- Remove calls to copyKillDeadInfo which is an N^2 function. Instead, propagate kill / dead markers as new instructions are constructed in foldMemoryOperand, convertToThressAddress, etc.

- Also remove LiveVariables::instructionChanged, etc. Replace all calls with cheaper calls which update VarInfo kill list.


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

14 files changed, 211 insertions, 222 deletions

diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index ccf7e9d..1d161cf 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -884,10 +884,6 @@ bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
 
     // Attempt to fold the memory reference into the instruction. If
     // we can do this, we don't need to insert spill code.
-    if (lv_)
-      lv_->instructionChanged(MI, fmi);
-    else
-      fmi->copyKillDeadInfo(MI, tri_);
     MachineBasicBlock &MBB = *MI->getParent();
     if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot))
       vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
@@ -1464,10 +1460,6 @@ std::vector<LiveInterval*> LiveIntervals::
 addIntervalsForSpills(const LiveInterval &li,
                       const MachineLoopInfo *loopInfo, VirtRegMap &vrm,
                       float &SSWeight) {
-  // Since this is called after the analysis is done we don't know if
-  // LiveVariables is available
-  lv_ = getAnalysisToUpdate<LiveVariables>();
-
   assert(li.weight != HUGE_VALF &&
          "attempt to spill already spilled interval!");
 
diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp
index 1689915..82016ed 100644
--- a/lib/CodeGen/LiveVariables.cpp
+++ b/lib/CodeGen/LiveVariables.cpp
@@ -653,37 +653,6 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) {
   return false;
 }
 
-/// instructionChanged - When the address of an instruction changes, this method
-/// should be called so that live variables can update its internal data
-/// structures.  This removes the records for OldMI, transfering them to the
-/// records for NewMI.
-void LiveVariables::instructionChanged(MachineInstr *OldMI,
-                                       MachineInstr *NewMI) {
-  // If the instruction defines any virtual registers, update the VarInfo,
-  // kill and dead information for the instruction.
-  for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) {
-    MachineOperand &MO = OldMI->getOperand(i);
-    if (MO.isRegister() && MO.getReg() &&
-        TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
-      unsigned Reg = MO.getReg();
-      VarInfo &VI = getVarInfo(Reg);
-      if (MO.isDef()) {
-        if (MO.isDead()) {
-          MO.setIsDead(false);
-          addVirtualRegisterDead(Reg, NewMI);
-        }
-      }
-      if (MO.isKill()) {
-        MO.setIsKill(false);
-        addVirtualRegisterKilled(Reg, NewMI);
-      }
-      // If this is a kill of the value, update the VI kills list.
-      if (VI.removeKill(OldMI))
-        VI.Kills.push_back(NewMI);   // Yes, there was a kill of it
-    }
-  }
-}
-
 /// replaceKillInstruction - Update register kill info by replacing a kill
 /// instruction with a new one.
 void LiveVariables::replaceKillInstruction(unsigned Reg, MachineInstr *OldMI,
@@ -708,22 +677,6 @@ void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) {
   }
 }
 
-/// removeVirtualRegistersDead - Remove all of the dead registers for the
-/// specified instruction from the live variable information.
-void LiveVariables::removeVirtualRegistersDead(MachineInstr *MI) {
-  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
-    MachineOperand &MO = MI->getOperand(i);
-    if (MO.isRegister() && MO.isDead()) {
-      MO.setIsDead(false);
-      unsigned Reg = MO.getReg();
-      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
-        bool removed = getVarInfo(Reg).removeKill(MI);
-        assert(removed && "kill not in register's VarInfo?");
-      }
-    }
-  }
-}
-
 /// analyzePHINodes - Gather information about the PHI nodes in here. In
 /// particular, we want to map the variable information of a virtual register
 /// which is used in a PHI node. We map that to the BB the vreg is coming from.
diff --git a/lib/CodeGen/MachineInstr.cpp b/lib/CodeGen/MachineInstr.cpp
index 8e9933c..fe78828 100644
--- a/lib/CodeGen/MachineInstr.cpp
+++ b/lib/CodeGen/MachineInstr.cpp
@@ -647,9 +647,9 @@ void MachineInstr::copyPredicates(const MachineInstr *MI) {
   }
 }
 
-/// isSafeToMove - Return true if it is safe to this instruction. If SawStore is
-/// set to true, it means that there is a store (or call) between the
-/// instruction's location and its intended destination.
+/// isSafeToMove - Return true if it is safe to move this instruction. If
+/// SawStore is set to true, it means that there is a store (or call) between
+/// the instruction's location and its intended destination.
 bool MachineInstr::isSafeToMove(const TargetInstrInfo *TII, bool &SawStore) {
   // Ignore stuff that we obviously can't move.
   if (TID->mayStore() || TID->isCall()) {
@@ -829,27 +829,3 @@ bool MachineInstr::addRegisterDead(unsigned IncomingReg,
   }
   return false;
 }
-
-/// copyKillDeadInfo - copies killed/dead information from one instr to another
-void MachineInstr::copyKillDeadInfo(MachineInstr *OldMI,
-                                    const TargetRegisterInfo *RegInfo) {
-  // If the instruction defines any virtual registers, update the VarInfo,
-  // kill and dead information for the instruction.
-  for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) {
-    MachineOperand &MO = OldMI->getOperand(i);
-    if (MO.isRegister() && MO.getReg() &&
-        TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
-      unsigned Reg = MO.getReg();
-      if (MO.isDef()) {
-        if (MO.isDead()) {
-          MO.setIsDead(false);
-          addRegisterDead(Reg, RegInfo);
-        }
-      }
-      if (MO.isKill()) {
-        MO.setIsKill(false);
-        addRegisterKilled(Reg, RegInfo);
-      }
-    }
-  }
-}
diff --git a/lib/CodeGen/PHIElimination.cpp b/lib/CodeGen/PHIElimination.cpp
index b50a008..6dbc3dc 100644
--- a/lib/CodeGen/PHIElimination.cpp
+++ b/lib/CodeGen/PHIElimination.cpp
@@ -152,36 +152,44 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB,
 
   unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2;
   unsigned DestReg = MPhi->getOperand(0).getReg();
+  bool isDead = MPhi->getOperand(0).isDead();
 
   // Create a new register for the incoming PHI arguments.
   MachineFunction &MF = *MBB.getParent();
   const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
-  unsigned IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
+  unsigned IncomingReg = 0;
 
   // Insert a register to register copy at the top of the current block (but
   // after any remaining phi nodes) which copies the new incoming register
   // into the phi node destination.
   const TargetInstrInfo *TII = MF.getTarget().getInstrInfo();
   if (isSourceDefinedByImplicitDef(MPhi, MRI))
-    // If all sources of a PHI node are implicit_def, just emit an implicit_def
-    // instead of a copy.
-    BuildMI(MBB, AfterPHIsIt, TII->get(TargetInstrInfo::IMPLICIT_DEF), DestReg);
-  else
+    // If all sources of a PHI node are implicit_def, just emit an
+    // implicit_def instead of a copy.
+    BuildMI(MBB, AfterPHIsIt,
+            TII->get(TargetInstrInfo::IMPLICIT_DEF), DestReg);
+  else {
+    IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
     TII->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC, RC);
+  }
 
   // Update live variable information if there is any.
   LiveVariables *LV = getAnalysisToUpdate<LiveVariables>();
   if (LV) {
     MachineInstr *PHICopy = prior(AfterPHIsIt);
 
-    // Increment use count of the newly created virtual register.
-    LV->getVarInfo(IncomingReg).NumUses++;
+    if (IncomingReg) {
+      // Increment use count of the newly created virtual register.
+      LV->getVarInfo(IncomingReg).NumUses++;
+
+      // Add information to LiveVariables to know that the incoming value is
+      // killed.  Note that because the value is defined in several places (once
+      // each for each incoming block), the "def" block and instruction fields
+      // for the VarInfo is not filled in.
+      LV->addVirtualRegisterKilled(IncomingReg, PHICopy);
 
-    // Add information to LiveVariables to know that the incoming value is
-    // killed.  Note that because the value is defined in several places (once
-    // each for each incoming block), the "def" block and instruction fields for
-    // the VarInfo is not filled in.
-    LV->addVirtualRegisterKilled(IncomingReg, PHICopy);
+      LV->getVarInfo(IncomingReg).UsedBlocks[MBB.getNumber()] = true;
+    }
 
     // Since we are going to be deleting the PHI node, if it is the last use of
     // any registers, or if the value itself is dead, we need to move this
@@ -189,12 +197,10 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB,
     LV->removeVirtualRegistersKilled(MPhi);
 
     // If the result is dead, update LV.
-    if (MPhi->registerDefIsDead(DestReg)) {
+    if (isDead) {
       LV->addVirtualRegisterDead(DestReg, PHICopy);
-      LV->removeVirtualRegistersDead(MPhi);
+      LV->removeVirtualRegisterDead(DestReg, MPhi);
     }
-
-    LV->getVarInfo(IncomingReg).UsedBlocks[MBB.getNumber()] = true;
   }
 
   // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
@@ -211,7 +217,7 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB,
            "Machine PHI Operands must all be virtual registers!");
 
     // If source is defined by an implicit def, there is no need to insert a
-    // copy unless it's the only source.
+    // copy.
     MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
     if (DefMI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
       ImpDefs.insert(DefMI);
diff --git a/lib/CodeGen/TwoAddressInstructionPass.cpp b/lib/CodeGen/TwoAddressInstructionPass.cpp
index 480d6dd..08f576c 100644
--- a/lib/CodeGen/TwoAddressInstructionPass.cpp
+++ b/lib/CodeGen/TwoAddressInstructionPass.cpp
@@ -184,11 +184,8 @@ bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB,
   KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI);
   KillMO->setIsKill(true);
   
-  if (LV) {
-    LiveVariables::VarInfo& VarInfo = LV->getVarInfo(SavedReg);
-    VarInfo.removeKill(KillMI);
-    VarInfo.Kills.push_back(MI);
-  }
+  if (LV)
+    LV->replaceKillInstruction(SavedReg, KillMI, MI);
 
   // Move instruction to its destination.
   MBB->remove(MI);
@@ -454,10 +451,10 @@ bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) {
             // regB is used in this BB.
             varInfoB.UsedBlocks[mbbi->getNumber()] = true;
 
-            if (LV->removeVirtualRegisterKilled(regB, mbbi, mi))
+            if (LV->removeVirtualRegisterKilled(regB,  mi))
               LV->addVirtualRegisterKilled(regB, prevMi);
 
-            if (LV->removeVirtualRegisterDead(regB, mbbi, mi))
+            if (LV->removeVirtualRegisterDead(regB, mi))
               LV->addVirtualRegisterDead(regB, prevMi);
           }
           
diff --git a/lib/Target/ARM/ARMInstrInfo.cpp b/lib/Target/ARM/ARMInstrInfo.cpp
index 61e4f26..95e4000 100644
--- a/lib/Target/ARM/ARMInstrInfo.cpp
+++ b/lib/Target/ARM/ARMInstrInfo.cpp
@@ -677,30 +677,35 @@ MachineInstr *ARMInstrInfo::foldMemoryOperand(MachineFunction &MF,
     unsigned PredReg = MI->getOperand(3).getReg();
     if (OpNum == 0) { // move -> store
       unsigned SrcReg = MI->getOperand(1).getReg();
-      NewMI = BuildMI(get(ARM::STR)).addReg(SrcReg).addFrameIndex(FI)
-        .addReg(0).addImm(0).addImm(Pred).addReg(PredReg);
+      bool isKill = MI->getOperand(1).isKill();
+      NewMI = BuildMI(get(ARM::STR)).addReg(SrcReg, false, false, isKill)
+        .addFrameIndex(FI).addReg(0).addImm(0).addImm(Pred).addReg(PredReg);
     } else {          // move -> load
       unsigned DstReg = MI->getOperand(0).getReg();
-      NewMI = BuildMI(get(ARM::LDR), DstReg).addFrameIndex(FI).addReg(0)
-        .addImm(0).addImm(Pred).addReg(PredReg);
+      bool isDead = MI->getOperand(0).isDead();
+      NewMI = BuildMI(get(ARM::LDR)).addReg(DstReg, true, false, false, isDead)
+        .addFrameIndex(FI).addReg(0).addImm(0).addImm(Pred).addReg(PredReg);
     }
     break;
   }
   case ARM::tMOVr: {
     if (OpNum == 0) { // move -> store
       unsigned SrcReg = MI->getOperand(1).getReg();
+      bool isKill = MI->getOperand(1).isKill();
       if (RI.isPhysicalRegister(SrcReg) && !RI.isLowRegister(SrcReg))
         // tSpill cannot take a high register operand.
         break;
-      NewMI = BuildMI(get(ARM::tSpill)).addReg(SrcReg).addFrameIndex(FI)
-        .addImm(0);
+      NewMI = BuildMI(get(ARM::tSpill)).addReg(SrcReg, false, false, isKill)
+        .addFrameIndex(FI).addImm(0);
     } else {          // move -> load
       unsigned DstReg = MI->getOperand(0).getReg();
       if (RI.isPhysicalRegister(DstReg) && !RI.isLowRegister(DstReg))
         // tRestore cannot target a high register operand.
         break;
-      NewMI = BuildMI(get(ARM::tRestore), DstReg).addFrameIndex(FI)
-        .addImm(0);
+      bool isDead = MI->getOperand(0).isDead();
+      NewMI = BuildMI(get(ARM::tRestore))
+        .addReg(DstReg, true, false, false, isDead)
+        .addFrameIndex(FI).addImm(0);
     }
     break;
   }
@@ -723,19 +728,19 @@ MachineInstr *ARMInstrInfo::foldMemoryOperand(MachineFunction &MF,
     unsigned PredReg = MI->getOperand(3).getReg();
     if (OpNum == 0) { // move -> store
       unsigned SrcReg = MI->getOperand(1).getReg();
-      NewMI = BuildMI(get(ARM::FSTD)).addReg(SrcReg).addFrameIndex(FI)
-        .addImm(0).addImm(Pred).addReg(PredReg);
+      bool isKill = MI->getOperand(1).isKill();
+      NewMI = BuildMI(get(ARM::FSTD)).addReg(SrcReg, false, false, isKill)
+        .addFrameIndex(FI).addImm(0).addImm(Pred).addReg(PredReg);
     } else {          // move -> load
       unsigned DstReg = MI->getOperand(0).getReg();
-      NewMI = BuildMI(get(ARM::FLDD), DstReg).addFrameIndex(FI)
-        .addImm(0).addImm(Pred).addReg(PredReg);
+      bool isDead = MI->getOperand(0).isDead();
+      NewMI = BuildMI(get(ARM::FLDD)).addReg(DstReg, true, false, false, isDead)
+        .addFrameIndex(FI).addImm(0).addImm(Pred).addReg(PredReg);
     }
     break;
   }
   }
 
-  if (NewMI)
-    NewMI->copyKillDeadInfo(MI);
   return NewMI;
 }
 
diff --git a/lib/Target/Alpha/AlphaInstrInfo.cpp b/lib/Target/Alpha/AlphaInstrInfo.cpp
index 96a75a6..6f96ff0 100644
--- a/lib/Target/Alpha/AlphaInstrInfo.cpp
+++ b/lib/Target/Alpha/AlphaInstrInfo.cpp
@@ -269,23 +269,25 @@ MachineInstr *AlphaInstrInfo::foldMemoryOperand(MachineFunction &MF,
      if (MI->getOperand(1).getReg() == MI->getOperand(2).getReg()) {
        if (Ops[0] == 0) {  // move -> store
          unsigned InReg = MI->getOperand(1).getReg();
+         bool isKill = MI->getOperand(1).isKill();
          Opc = (Opc == Alpha::BISr) ? Alpha::STQ : 
            ((Opc == Alpha::CPYSS) ? Alpha::STS : Alpha::STT);
-         NewMI = BuildMI(get(Opc)).addReg(InReg).addFrameIndex(FrameIndex)
+         NewMI = BuildMI(get(Opc)).addReg(InReg, false, false, isKill)
+           .addFrameIndex(FrameIndex)
            .addReg(Alpha::F31);
        } else {           // load -> move
          unsigned OutReg = MI->getOperand(0).getReg();
+         bool isDead = MI->getOperand(0).isDead();
          Opc = (Opc == Alpha::BISr) ? Alpha::LDQ : 
            ((Opc == Alpha::CPYSS) ? Alpha::LDS : Alpha::LDT);
-         NewMI = BuildMI(get(Opc), OutReg).addFrameIndex(FrameIndex)
+         NewMI = BuildMI(get(Opc)).addReg(OutReg, true, false, false, isDead)
+           .addFrameIndex(FrameIndex)
            .addReg(Alpha::F31);
        }
      }
      break;
    }
-  if (NewMI)
-    NewMI->copyKillDeadInfo(MI);
-  return 0;
+  return NewMI;
 }
 
 static unsigned AlphaRevCondCode(unsigned Opcode) {
diff --git a/lib/Target/CellSPU/SPUInstrInfo.cpp b/lib/Target/CellSPU/SPUInstrInfo.cpp
index 3e991a9..aef3611 100644
--- a/lib/Target/CellSPU/SPUInstrInfo.cpp
+++ b/lib/Target/CellSPU/SPUInstrInfo.cpp
@@ -412,20 +412,22 @@ SPUInstrInfo::foldMemoryOperand(MachineFunction &MF,
        && MI->getOperand(1).getReg() == MI->getOperand(2).getReg()) {
     if (OpNum == 0) {  // move -> store
       unsigned InReg = MI->getOperand(1).getReg();
+      bool isKill = MI->getOperand(1).isKill();
       if (FrameIndex < SPUFrameInfo::maxFrameOffset()) {
-        NewMI = addFrameReference(BuildMI(TII.get(SPU::STQDr32)).addReg(InReg),
+        NewMI = addFrameReference(BuildMI(TII.get(SPU::STQDr32))
+                                  .addReg(InReg, false, false, isKill),
                                   FrameIndex);
       }
     } else {           // move -> load
       unsigned OutReg = MI->getOperand(0).getReg();
-      Opc = (FrameIndex < SPUFrameInfo::maxFrameOffset()) ? SPU::STQDr32 : SPU::STQXr32;
-      NewMI = addFrameReference(BuildMI(TII.get(Opc), OutReg), FrameIndex);
+      bool isDead = MI->getOperand(0).isDead();
+      Opc = (FrameIndex < SPUFrameInfo::maxFrameOffset())
+        ? SPU::STQDr32 : SPU::STQXr32;
+      NewMI = addFrameReference(BuildMI(TII.get(Opc))
+                       .addReg(OutReg, true, false, false, isDead), FrameIndex);
     }
   }
 
-  if (NewMI)
-    NewMI->copyKillDeadInfo(MI);
-
   return NewMI;
 #else
   return 0;
diff --git a/lib/Target/Mips/MipsInstrInfo.cpp b/lib/Target/Mips/MipsInstrInfo.cpp
index fa5d8b3..c7bc1e9 100644
--- a/lib/Target/Mips/MipsInstrInfo.cpp
+++ b/lib/Target/Mips/MipsInstrInfo.cpp
@@ -386,18 +386,22 @@ foldMemoryOperand(MachineFunction &MF,
         (MI->getOperand(1).getReg() == Mips::ZERO) &&
         (MI->getOperand(2).isRegister())) 
       {
-        if (Ops[0] == 0)    // COPY -> STORE
+        if (Ops[0] == 0) {    // COPY -> STORE
+          unsigned SrcReg = MI->getOperand(2).getReg();
+          bool isKill = MI->getOperand(2).isKill();
           NewMI = BuildMI(get(Mips::SW)).addFrameIndex(FI)
-                  .addImm(0).addReg(MI->getOperand(2).getReg());
-        else                   // COPY -> LOAD
-          NewMI = BuildMI(get(Mips::LW), MI->getOperand(0)
-                  .getReg()).addImm(0).addFrameIndex(FI);
+            .addImm(0).addReg(SrcReg, false, false, isKill);
+        } else {              // COPY -> LOAD
+          unsigned DstReg = MI->getOperand(0).getReg();
+          bool isDead = MI->getOperand(0).isDead();
+          NewMI = BuildMI(get(Mips::LW))
+            .addReg(DstReg, true, false, false, isDead)
+            .addImm(0).addFrameIndex(FI);
+        }
       }
       break;
   }
 
-  if (NewMI)
-    NewMI->copyKillDeadInfo(MI);
   return NewMI;
 }
 
diff --git a/lib/Target/PowerPC/PPCInstrInfo.cpp b/lib/Target/PowerPC/PPCInstrInfo.cpp
index 378fa4b..a387f38 100644
--- a/lib/Target/PowerPC/PPCInstrInfo.cpp
+++ b/lib/Target/PowerPC/PPCInstrInfo.cpp
@@ -661,45 +661,62 @@ MachineInstr *PPCInstrInfo::foldMemoryOperand(MachineFunction &MF,
        MI->getOperand(1).getReg() == MI->getOperand(2).getReg())) {
     if (OpNum == 0) {  // move -> store
       unsigned InReg = MI->getOperand(1).getReg();
-      NewMI = addFrameReference(BuildMI(get(PPC::STW)).addReg(InReg),
+      bool isKill = MI->getOperand(1).isKill();
+      NewMI = addFrameReference(BuildMI(get(PPC::STW))
+                                .addReg(InReg, false, false, isKill),
                                 FrameIndex);
     } else {           // move -> load
       unsigned OutReg = MI->getOperand(0).getReg();
-      NewMI = addFrameReference(BuildMI(get(PPC::LWZ), OutReg),
+      bool isDead = MI->getOperand(0).isDead();
+      NewMI = addFrameReference(BuildMI(get(PPC::LWZ))
+                                .addReg(OutReg, true, false, false, isDead),
                                 FrameIndex);
     }
   } else if ((Opc == PPC::OR8 &&
               MI->getOperand(1).getReg() == MI->getOperand(2).getReg())) {
     if (OpNum == 0) {  // move -> store
       unsigned InReg = MI->getOperand(1).getReg();
-      NewMI = addFrameReference(BuildMI(get(PPC::STD)).addReg(InReg),
+      bool isKill = MI->getOperand(1).isKill();
+      NewMI = addFrameReference(BuildMI(get(PPC::STD))
+                                .addReg(InReg, false, false, isKill),
                                 FrameIndex);
     } else {           // move -> load
       unsigned OutReg = MI->getOperand(0).getReg();
-      NewMI = addFrameReference(BuildMI(get(PPC::LD), OutReg), FrameIndex);
+      bool isDead = MI->getOperand(0).isDead();
+      NewMI = addFrameReference(BuildMI(get(PPC::LD))
+                                .addReg(OutReg, true, false, false, isDead),
+                                FrameIndex);
     }
   } else if (Opc == PPC::FMRD) {
     if (OpNum == 0) {  // move -> store
       unsigned InReg = MI->getOperand(1).getReg();
-      NewMI = addFrameReference(BuildMI(get(PPC::STFD)).addReg(InReg),
+      bool isKill = MI->getOperand(1).isKill();
+      NewMI = addFrameReference(BuildMI(get(PPC::STFD))
+                                .addReg(InReg, false, false, isKill),
                                 FrameIndex);
     } else {           // move -> load
       unsigned OutReg = MI->getOperand(0).getReg();
-      NewMI = addFrameReference(BuildMI(get(PPC::LFD), OutReg), FrameIndex);
+      bool isDead = MI->getOperand(0).isDead();
+      NewMI = addFrameReference(BuildMI(get(PPC::LFD))
+                                .addReg(OutReg, true, false, false, isDead),
+                                FrameIndex);
     }
   } else if (Opc == PPC::FMRS) {
     if (OpNum == 0) {  // move -> store
       unsigned InReg = MI->getOperand(1).getReg();
-      NewMI = addFrameReference(BuildMI(get(PPC::STFS)).addReg(InReg),
+      bool isKill = MI->getOperand(1).isKill();
+      NewMI = addFrameReference(BuildMI(get(PPC::STFS))
+                                .addReg(InReg, false, false, isKill),
                                 FrameIndex);
     } else {           // move -> load
       unsigned OutReg = MI->getOperand(0).getReg();
-      NewMI = addFrameReference(BuildMI(get(PPC::LFS), OutReg), FrameIndex);
+      bool isDead = MI->getOperand(0).isDead();
+      NewMI = addFrameReference(BuildMI(get(PPC::LFS))
+                                .addReg(OutReg, true, false, false, isDead),
+                                FrameIndex);
     }
   }
 
-  if (NewMI)
-    NewMI->copyKillDeadInfo(MI);
   return NewMI;
 }
 
diff --git a/lib/Target/Sparc/SparcInstrInfo.cpp b/lib/Target/Sparc/SparcInstrInfo.cpp
index 79fc912..67df87b 100644
--- a/lib/Target/Sparc/SparcInstrInfo.cpp
+++ b/lib/Target/Sparc/SparcInstrInfo.cpp
@@ -247,16 +247,19 @@ MachineInstr *SparcInstrInfo::foldMemoryOperand(MachineFunction &MF,
     isFloat = true;
     // FALLTHROUGH
   case SP::FMOVD:
-    if (OpNum == 0)  // COPY -> STORE
+    if (OpNum == 0) { // COPY -> STORE
+      unsigned SrcReg = MI->getOperand(1).getReg();
+      bool isKill = MI->getOperand(1).isKill();
       NewMI = BuildMI(get(isFloat ? SP::STFri : SP::STDFri))
-               .addFrameIndex(FI).addImm(0).addReg(MI->getOperand(1).getReg());
-    else             // COPY -> LOAD
-      NewMI = BuildMI(get(isFloat ? SP::LDFri : SP::LDDFri),
-                     MI->getOperand(0).getReg()).addFrameIndex(FI).addImm(0);
+        .addFrameIndex(FI).addImm(0).addReg(SrcReg, false, false, isKill);
+    } else {             // COPY -> LOAD
+      unsigned DstReg = MI->getOperand(0).getReg();
+      bool isDead = MI->getOperand(0).isDead();
+      NewMI = BuildMI(get(isFloat ? SP::LDFri : SP::LDDFri))
+        .addReg(DstReg, true, false, false, isDead).addFrameIndex(FI).addImm(0);
+    }
     break;
   }
 
-  if (NewMI)
-    NewMI->copyKillDeadInfo(MI);
   return NewMI;
 }
diff --git a/lib/Target/X86/X86InstrBuilder.h b/lib/Target/X86/X86InstrBuilder.h
index e5336bc..428f24e 100644
--- a/lib/Target/X86/X86InstrBuilder.h
+++ b/lib/Target/X86/X86InstrBuilder.h
@@ -70,15 +70,19 @@ inline const MachineInstrBuilder &addDirectMem(const MachineInstrBuilder &MIB,
 /// displacement. An example is: DWORD PTR [EAX + 4].
 ///
 inline const MachineInstrBuilder &addRegOffset(const MachineInstrBuilder &MIB,
-                                               unsigned Reg, int Offset) {
-  return MIB.addReg(Reg).addImm(1).addReg(0).addImm(Offset);
+                                               unsigned Reg, bool isKill,
+                                               int Offset) {
+  return MIB.addReg(Reg, false, false, isKill)
+    .addImm(1).addReg(0).addImm(Offset);
 }
 
 /// addRegReg - This function is used to add a memory reference of the form:
 /// [Reg + Reg].
 inline const MachineInstrBuilder &addRegReg(const MachineInstrBuilder &MIB,
-                                            unsigned Reg1, unsigned Reg2) {
-  return MIB.addReg(Reg1).addImm(1).addReg(Reg2).addImm(0);
+                                            unsigned Reg1, bool isKill1,
+                                            unsigned Reg2, bool isKill2) {
+  return MIB.addReg(Reg1, false, false, isKill1).addImm(1)
+    .addReg(Reg2, false, false, isKill2).addImm(0);
 }
 
 inline const MachineInstrBuilder &addFullAddress(const MachineInstrBuilder &MIB,
diff --git a/lib/Target/X86/X86InstrInfo.cpp b/lib/Target/X86/X86InstrInfo.cpp
index 2a3f1cb..c833de5 100644
--- a/lib/Target/X86/X86InstrInfo.cpp
+++ b/lib/Target/X86/X86InstrInfo.cpp
@@ -983,6 +983,8 @@ X86InstrInfo::convertToThreeAddress(MachineFunction::iterator &MFI,
   // All instructions input are two-addr instructions.  Get the known operands.
   unsigned Dest = MI->getOperand(0).getReg();
   unsigned Src = MI->getOperand(1).getReg();
+  bool isDead = MI->getOperand(0).isDead();
+  bool isKill = MI->getOperand(1).isKill();
 
   MachineInstr *NewMI = NULL;
   // FIXME: 16-bit LEA's are really slow on Athlons, but not bad on P4's.  When
@@ -995,51 +997,47 @@ X86InstrInfo::convertToThreeAddress(MachineFunction::iterator &MFI,
     assert(MI->getNumOperands() == 4 && "Unknown shufps instruction!");
     if (!TM.getSubtarget<X86Subtarget>().hasSSE2()) return 0;
     
-    unsigned A = MI->getOperand(0).getReg();
     unsigned B = MI->getOperand(1).getReg();
     unsigned C = MI->getOperand(2).getReg();
-    unsigned M = MI->getOperand(3).getImm();
     if (B != C) return 0;
-    NewMI = BuildMI(get(X86::PSHUFDri), A).addReg(B).addImm(M);
+    unsigned A = MI->getOperand(0).getReg();
+    unsigned M = MI->getOperand(3).getImm();
+    NewMI = BuildMI(get(X86::PSHUFDri)).addReg(A, true, false, false, isDead)
+      .addReg(B, false, false, isKill).addImm(M);
     break;
   }
   case X86::SHL64ri: {
     assert(MI->getNumOperands() >= 3 && "Unknown shift instruction!");
     // NOTE: LEA doesn't produce flags like shift does, but LLVM never uses
     // the flags produced by a shift yet, so this is safe.
-    unsigned Dest = MI->getOperand(0).getReg();
-    unsigned Src = MI->getOperand(1).getReg();
     unsigned ShAmt = MI->getOperand(2).getImm();
     if (ShAmt == 0 || ShAmt >= 4) return 0;
-    
-    NewMI = BuildMI(get(X86::LEA64r), Dest)
-      .addReg(0).addImm(1 << ShAmt).addReg(Src).addImm(0);
+
+    NewMI = BuildMI(get(X86::LEA64r)).addReg(Dest, true, false, false, isDead)
+      .addReg(0).addImm(1 << ShAmt).addReg(Src, false, false, isKill).addImm(0);
     break;
   }
   case X86::SHL32ri: {
     assert(MI->getNumOperands() >= 3 && "Unknown shift instruction!");
     // NOTE: LEA doesn't produce flags like shift does, but LLVM never uses
     // the flags produced by a shift yet, so this is safe.
-    unsigned Dest = MI->getOperand(0).getReg();
-    unsigned Src = MI->getOperand(1).getReg();
     unsigned ShAmt = MI->getOperand(2).getImm();
     if (ShAmt == 0 || ShAmt >= 4) return 0;
-    
+
     unsigned Opc = TM.getSubtarget<X86Subtarget>().is64Bit() ?
       X86::LEA64_32r : X86::LEA32r;
-    NewMI = BuildMI(get(Opc), Dest)
-      .addReg(0).addImm(1 << ShAmt).addReg(Src).addImm(0);
+    NewMI = BuildMI(get(Opc)).addReg(Dest, true, false, false, isDead)
+      .addReg(0).addImm(1 << ShAmt)
+      .addReg(Src, false, false, isKill).addImm(0);
     break;
   }
   case X86::SHL16ri: {
     assert(MI->getNumOperands() >= 3 && "Unknown shift instruction!");
     // NOTE: LEA doesn't produce flags like shift does, but LLVM never uses
     // the flags produced by a shift yet, so this is safe.
-    unsigned Dest = MI->getOperand(0).getReg();
-    unsigned Src = MI->getOperand(1).getReg();
     unsigned ShAmt = MI->getOperand(2).getImm();
     if (ShAmt == 0 || ShAmt >= 4) return 0;
-    
+
     if (DisableLEA16) {
       // If 16-bit LEA is disabled, use 32-bit LEA via subregisters.
       MachineRegisterInfo &RegInfo = MFI->getParent()->getRegInfo();
@@ -1050,33 +1048,36 @@ X86InstrInfo::convertToThreeAddress(MachineFunction::iterator &MFI,
             
       // Build and insert into an implicit UNDEF value. This is OK because
       // well be shifting and then extracting the lower 16-bits. 
-      MachineInstr *Undef = BuildMI(get(X86::IMPLICIT_DEF), leaInReg);
+      MachineInstr *Undef = BuildMI(get(X86::IMPLICIT_DEF), leaInReg);      
+      MachineInstr *InsMI =  BuildMI(get(X86::INSERT_SUBREG),leaInReg)
+        .addReg(leaInReg).addReg(Src, false, false, isKill)
+        .addImm(X86::SUBREG_16BIT);
       
-      MachineInstr *Ins = 
-       BuildMI(get(X86::INSERT_SUBREG),leaInReg)
-                    .addReg(leaInReg).addReg(Src).addImm(X86::SUBREG_16BIT);
+      NewMI = BuildMI(get(Opc), leaOutReg).addReg(0).addImm(1 << ShAmt)
+        .addReg(leaInReg, false, false, true).addImm(0);
       
-      NewMI = BuildMI(get(Opc), leaOutReg)
-        .addReg(0).addImm(1 << ShAmt).addReg(leaInReg).addImm(0);
-      
-      MachineInstr *Ext =
-        BuildMI(get(X86::EXTRACT_SUBREG), Dest)
-         .addReg(leaOutReg).addImm(X86::SUBREG_16BIT);
-      Ext->copyKillDeadInfo(MI);
+      MachineInstr *ExtMI = BuildMI(get(X86::EXTRACT_SUBREG))
+        .addReg(Dest, true, false, false, isDead)
+        .addReg(leaOutReg, false, false, true).addImm(X86::SUBREG_16BIT);
       
       MFI->insert(MBBI, Undef);
-      MFI->insert(MBBI, Ins);            // Insert the insert_subreg
+      MFI->insert(MBBI, InsMI);            // Insert the insert_subreg
+      MFI->insert(MBBI, NewMI);            // Insert the lea inst
+      MFI->insert(MBBI, ExtMI);            // Insert the extract_subreg      
       if (LV) {
-        LV->instructionChanged(MI, NewMI);  // Update live variables
-        LV->addVirtualRegisterKilled(leaInReg, NewMI);
+        // Update live variables
+        LV->getVarInfo(leaInReg).Kills.push_back(NewMI);
+        LV->getVarInfo(leaOutReg).Kills.push_back(ExtMI);
+        if (isKill)
+          LV->replaceKillInstruction(Src, MI, InsMI);
+        if (isDead)
+          LV->replaceKillInstruction(Dest, MI, ExtMI);
       }
-      MFI->insert(MBBI, NewMI);          // Insert the new inst
-      if (LV) LV->addVirtualRegisterKilled(leaOutReg, Ext);
-      MFI->insert(MBBI, Ext);            // Insert the extract_subreg      
-      return Ext;
+      return ExtMI;
     } else {
-      NewMI = BuildMI(get(X86::LEA16r), Dest)
-        .addReg(0).addImm(1 << ShAmt).addReg(Src).addImm(0);
+      NewMI = BuildMI(get(X86::LEA16r)).addReg(Dest, true, false, false, isDead)
+        .addReg(0).addImm(1 << ShAmt)
+        .addReg(Src, false, false, isKill).addImm(0);
     }
     break;
   }
@@ -1095,58 +1096,79 @@ X86InstrInfo::convertToThreeAddress(MachineFunction::iterator &MFI,
       assert(MI->getNumOperands() >= 2 && "Unknown inc instruction!");
       unsigned Opc = MIOpc == X86::INC64r ? X86::LEA64r
         : (is64Bit ? X86::LEA64_32r : X86::LEA32r);
-      NewMI = addRegOffset(BuildMI(get(Opc), Dest), Src, 1);
+      NewMI = addRegOffset(BuildMI(get(Opc))
+                           .addReg(Dest, true, false, false, isDead),
+                           Src, isKill, 1);
       break;
     }
     case X86::INC16r:
     case X86::INC64_16r:
       if (DisableLEA16) return 0;
       assert(MI->getNumOperands() >= 2 && "Unknown inc instruction!");
-      NewMI = addRegOffset(BuildMI(get(X86::LEA16r), Dest), Src, 1);
+      NewMI = addRegOffset(BuildMI(get(X86::LEA16r))
+                           .addReg(Dest, true, false, false, isDead),
+                           Src, isKill, 1);
       break;
     case X86::DEC64r:
     case X86::DEC32r: {
       assert(MI->getNumOperands() >= 2 && "Unknown dec instruction!");
       unsigned Opc = MIOpc == X86::DEC64r ? X86::LEA64r
         : (is64Bit ? X86::LEA64_32r : X86::LEA32r);
-      NewMI = addRegOffset(BuildMI(get(Opc), Dest), Src, -1);
+      NewMI = addRegOffset(BuildMI(get(Opc))
+                           .addReg(Dest, true, false, false, isDead),
+                           Src, isKill, -1);
       break;
     }
     case X86::DEC16r:
     case X86::DEC64_16r:
       if (DisableLEA16) return 0;
       assert(MI->getNumOperands() >= 2 && "Unknown dec instruction!");
-      NewMI = addRegOffset(BuildMI(get(X86::LEA16r), Dest), Src, -1);
+      NewMI = addRegOffset(BuildMI(get(X86::LEA16r))
+                           .addReg(Dest, true, false, false, isDead),
+                           Src, isKill, -1);
       break;
     case X86::ADD64rr:
     case X86::ADD32rr: {
       assert(MI->getNumOperands() >= 3 && "Unknown add instruction!");
       unsigned Opc = MIOpc == X86::ADD64rr ? X86::LEA64r
         : (is64Bit ? X86::LEA64_32r : X86::LEA32r);
-      NewMI = addRegReg(BuildMI(get(Opc), Dest), Src,
-                        MI->getOperand(2).getReg());
+      unsigned Src2 = MI->getOperand(2).getReg();
+      bool isKill2 = MI->getOperand(2).isKill();
+      NewMI = addRegReg(BuildMI(get(Opc))
+                        .addReg(Dest, true, false, false, isDead),
+                        Src, isKill, Src2, isKill2);
+      if (LV && isKill2)
+        LV->replaceKillInstruction(Src2, MI, NewMI);
       break;
     }
-    case X86::ADD16rr:
+    case X86::ADD16rr: {
       if (DisableLEA16) return 0;
       assert(MI->getNumOperands() >= 3 && "Unknown add instruction!");
-      NewMI = addRegReg(BuildMI(get(X86::LEA16r), Dest), Src,
-                        MI->getOperand(2).getReg());
+      unsigned Src2 = MI->getOperand(2).getReg();
+      bool isKill2 = MI->getOperand(2).isKill();
+      NewMI = addRegReg(BuildMI(get(X86::LEA16r))
+                        .addReg(Dest, true, false, false, isDead),
+                        Src, isKill, Src2, isKill2);
+      if (LV && isKill2)
+        LV->replaceKillInstruction(Src2, MI, NewMI);
       break;
+    }
     case X86::ADD64ri32:
     case X86::ADD64ri8:
       assert(MI->getNumOperands() >= 3 && "Unknown add instruction!");
       if (MI->getOperand(2).isImmediate())
-        NewMI = addRegOffset(BuildMI(get(X86::LEA64r), Dest), Src,
-                             MI->getOperand(2).getImm());
+        NewMI = addRegOffset(BuildMI(get(X86::LEA64r))
+                             .addReg(Dest, true, false, false, isDead),
+                             Src, isKill, MI->getOperand(2).getImm());
       break;
     case X86::ADD32ri:
     case X86::ADD32ri8:
       assert(MI->getNumOperands() >= 3 && "Unknown add instruction!");
       if (MI->getOperand(2).isImmediate()) {
         unsigned Opc = is64Bit ? X86::LEA64_32r : X86::LEA32r;
-        NewMI = addRegOffset(BuildMI(get(Opc), Dest), Src,
-                             MI->getOperand(2).getImm());
+        NewMI = addRegOffset(BuildMI(get(Opc))
+                             .addReg(Dest, true, false, false, isDead),
+                             Src, isKill, MI->getOperand(2).getImm());
       }
       break;
     case X86::ADD16ri:
@@ -1154,8 +1176,9 @@ X86InstrInfo::convertToThreeAddress(MachineFunction::iterator &MFI,
       if (DisableLEA16) return 0;
       assert(MI->getNumOperands() >= 3 && "Unknown add instruction!");
       if (MI->getOperand(2).isImmediate())
-        NewMI = addRegOffset(BuildMI(get(X86::LEA16r), Dest), Src,
-                             MI->getOperand(2).getImm());
+        NewMI = addRegOffset(BuildMI(get(X86::LEA16r))
+                             .addReg(Dest, true, false, false, isDead),
+                             Src, isKill, MI->getOperand(2).getImm());
       break;
     case X86::SHL16ri:
       if (DisableLEA16) return 0;
@@ -1171,7 +1194,10 @@ X86InstrInfo::convertToThreeAddress(MachineFunction::iterator &MFI,
         unsigned Opc = MIOpc == X86::SHL64ri ? X86::LEA64r
           : (MIOpc == X86::SHL32ri
              ? (is64Bit ? X86::LEA64_32r : X86::LEA32r) : X86::LEA16r);
-        NewMI = addFullAddress(BuildMI(get(Opc), Dest), AM);
+        NewMI = addFullAddress(BuildMI(get(Opc))
+                               .addReg(Dest, true, false, false, isDead), AM);
+        if (isKill)
+          NewMI->getOperand(3).setIsKill(true);
       }
       break;
     }
@@ -1181,8 +1207,13 @@ X86InstrInfo::convertToThreeAddress(MachineFunction::iterator &MFI,
 
   if (!NewMI) return 0;
 
-  NewMI->copyKillDeadInfo(MI);
-  if (LV) LV->instructionChanged(MI, NewMI);  // Update live variables
+  if (LV) {  // Update live variables
+    if (isKill)
+      LV->replaceKillInstruction(Src, MI, NewMI);
+    if (isDead)
+      LV->replaceKillInstruction(Dest, MI, NewMI);
+  }
+
   MFI->insert(MBBI, NewMI);          // Insert the new inst    
   return NewMI;
 }
@@ -1507,7 +1538,7 @@ static const MachineInstrBuilder &X86InstrAddOperand(MachineInstrBuilder &MIB,
                                                      MachineOperand &MO) {
   if (MO.isRegister())
     MIB = MIB.addReg(MO.getReg(), MO.isDef(), MO.isImplicit(),
-                     false, false, MO.getSubReg());
+                     MO.isKill(), MO.isDead(), MO.getSubReg());
   else if (MO.isImmediate())
     MIB = MIB.addImm(MO.getImm());
   else if (MO.isFrameIndex())
@@ -1769,8 +1800,8 @@ void X86InstrInfo::loadRegFromStackSlot(MachineBasicBlock &MBB,
 }
 
 void X86InstrInfo::loadRegFromAddr(MachineFunction &MF, unsigned DestReg,
-                                      SmallVectorImpl<MachineOperand> &Addr,
-                                      const TargetRegisterClass *RC,
+                                 SmallVectorImpl<MachineOperand> &Addr,
+                                 const TargetRegisterClass *RC,
                                  SmallVectorImpl<MachineInstr*> &NewMIs) const {
   unsigned Opc = getLoadRegOpcode(RC, RI.getStackAlignment());
   MachineInstrBuilder MIB = BuildMI(get(Opc), DestReg);
@@ -1906,10 +1937,8 @@ X86InstrInfo::foldMemoryOperand(MachineInstr *MI, unsigned i,
       NewMI = MakeM0Inst(*this, X86::MOV64mi32, MOs, MI);
     else if (MI->getOpcode() == X86::MOV8r0)
       NewMI = MakeM0Inst(*this, X86::MOV8mi, MOs, MI);
-    if (NewMI) {
-      NewMI->copyKillDeadInfo(MI);
+    if (NewMI)
       return NewMI;
-    }
     
     OpcodeTablePtr = &RegOp2MemOpTable0;
   } else if (i == 1) {
@@ -1928,7 +1957,6 @@ X86InstrInfo::foldMemoryOperand(MachineInstr *MI, unsigned i,
         NewMI = FuseTwoAddrInst(I->second, MOs, MI, *this);
       else
         NewMI = FuseInst(I->second, i, MOs, MI, *this);
-      NewMI->copyKillDeadInfo(MI);
       return NewMI;
     }
   }
diff --git a/lib/Target/X86/X86RegisterInfo.cpp b/lib/Target/X86/X86RegisterInfo.cpp
index 7270cd3..691e35f 100644
--- a/lib/Target/X86/X86RegisterInfo.cpp
+++ b/lib/Target/X86/X86RegisterInfo.cpp
@@ -750,7 +750,7 @@ void X86RegisterInfo::emitPrologue(MachineFunction &MF) const {
           .addExternalSymbol("_alloca");
         // Restore EAX
         MachineInstr *MI = addRegOffset(BuildMI(TII.get(X86::MOV32rm),X86::EAX),
-                                        StackPtr, NumBytes-4);
+                                        StackPtr, false, NumBytes-4);
         MBB.insert(MBBI, MI);
       }
     } else {
@@ -846,7 +846,7 @@ void X86RegisterInfo::emitEpilogue(MachineFunction &MF,
     if (CSSize) {
       unsigned Opc = Is64Bit ? X86::LEA64r : X86::LEA32r;
       MachineInstr *MI = addRegOffset(BuildMI(TII.get(Opc), StackPtr),
-                                      FramePtr, -CSSize);
+                                      FramePtr, false, -CSSize);
       MBB.insert(MBBI, MI);
     } else
       BuildMI(MBB, MBBI, TII.get(Is64Bit ? X86::MOV64rr : X86::MOV32rr),StackPtr).