6 files changed, 438 insertions, 58 deletions

diff --git a/include/llvm/CodeGen/MachineInstr.h b/include/llvm/CodeGen/MachineInstr.h
index fa372f6..7c8fe88 100644
--- a/include/llvm/CodeGen/MachineInstr.h
+++ b/include/llvm/CodeGen/MachineInstr.h
@@ -45,6 +45,7 @@ class MachineInstr {
 
   // Intrusive list support
   friend struct ilist_traits<MachineInstr>;
+  friend struct ilist_traits<MachineBasicBlock>;
   void setParent(MachineBasicBlock *P) { Parent = P; }
 public:
   /// MachineInstr ctor - This constructor creates a dummy MachineInstr with
@@ -154,27 +155,14 @@ public:
   void dump() const;
 
   //===--------------------------------------------------------------------===//
-  // Accessors to add operands when building up machine instructions.
-  //
-  void addOperand(const MachineOperand &Op) {
-    bool isImpReg = Op.isRegister() && Op.isImplicit();
-    assert((isImpReg || !OperandsComplete()) &&
-           "Trying to add an operand to a machine instr that is already done!");
-    if (isImpReg || NumImplicitOps == 0) {// This is true most of the time.
-      Operands.push_back(Op);
-      Operands.back().ParentMI = this;
-    } else {
-      // Insert a real operand before any implicit ones.
-      unsigned OpNo = Operands.size()-NumImplicitOps;
-      Operands.insert(Operands.begin()+OpNo, Op);
-      Operands[OpNo].ParentMI = this;
-    }
-  }
-  
-  //===--------------------------------------------------------------------===//
-  // Accessors used to modify instructions in place.
-  //
+  // Accessors used to build up machine instructions.
 
+  /// addOperand - Add the specified operand to the instruction.  If it is an
+  /// implicit operand, it is added to the end of the operand list.  If it is
+  /// an explicit operand it is added at the end of the explicit operand list
+  /// (before the first implicit operand). 
+  void addOperand(const MachineOperand &Op);
+  
   /// setInstrDescriptor - Replace the instruction descriptor (thus opcode) of
   /// the current instruction with a new one.
   ///
@@ -183,14 +171,27 @@ public:
   /// RemoveOperand - Erase an operand  from an instruction, leaving it with one
   /// fewer operand than it started with.
   ///
-  void RemoveOperand(unsigned i) {
-    Operands.erase(Operands.begin()+i);
-  }
+  void RemoveOperand(unsigned i);
+
 private:
+  /// getRegInfo - If this instruction is embedded into a MachineFunction,
+  /// return the MachineRegisterInfo object for the current function, otherwise
+  /// return null.
+  MachineRegisterInfo *getRegInfo();
 
   /// addImplicitDefUseOperands - Add all implicit def and use operands to
   /// this instruction.
   void addImplicitDefUseOperands();
+  
+  /// RemoveRegOperandsFromUseLists - Unlink all of the register operands in
+  /// this instruction from their respective use lists.  This requires that the
+  /// operands already be on their use lists.
+  void RemoveRegOperandsFromUseLists();
+  
+  /// AddRegOperandsToUseLists - Add all of the register operands in
+  /// this instruction from their respective use lists.  This requires that the
+  /// operands not be on their use lists yet.
+  void AddRegOperandsToUseLists(MachineRegisterInfo &RegInfo);
 };
 
 //===----------------------------------------------------------------------===//
diff --git a/include/llvm/CodeGen/MachineOperand.h b/include/llvm/CodeGen/MachineOperand.h
index 3bcd53b..66f106a 100644
--- a/include/llvm/CodeGen/MachineOperand.h
+++ b/include/llvm/CodeGen/MachineOperand.h
@@ -25,6 +25,7 @@ class MachineBasicBlock;
 class GlobalValue;
 class MachineInstr;
 class TargetMachine;
+class MachineRegisterInfo;
   
 /// MachineOperand class - Representation of each machine instruction operand.
 ///
@@ -76,8 +77,13 @@ private:
   /// Contents union - This contains the payload for the various operand types.
   union {
     MachineBasicBlock *MBB;   // For MO_MachineBasicBlock.
-    unsigned RegNo;           // For MO_Register.
     int64_t ImmVal;           // For MO_Immediate.
+
+    struct {                  // For MO_Register.
+      unsigned RegNo;
+      MachineOperand **Prev;  // Access list for register.
+      MachineOperand *Next;
+    } Reg;
     
     /// OffsetedInfo - This struct contains the offset and an object identifier.
     /// this represent the object as with an optional offset from it.
@@ -92,7 +98,6 @@ private:
   } Contents;
   
   MachineOperand(MachineOperandType K) : OpKind(K), ParentMI(0) {}
-
 public:
   MachineOperand(const MachineOperand &M) {
     *this = M;
@@ -138,7 +143,7 @@ public:
   /// getReg - Returns the register number.
   unsigned getReg() const {
     assert(isRegister() && "This is not a register operand!");
-    return Contents.RegNo;
+    return Contents.Reg.RegNo;
   }
   
   unsigned getSubReg() const {
@@ -175,11 +180,10 @@ public:
   // Mutators for Register Operands
   //===--------------------------------------------------------------------===//
   
-  void setReg(unsigned Reg) {
-    assert(isRegister() && "This is not a register operand!");
-    Contents.RegNo = Reg;
-  }
-
+  /// Change the register this operand corresponds to.
+  ///
+  void setReg(unsigned Reg);
+  
   void setSubReg(unsigned subReg) {
     assert(isRegister() && "Wrong MachineOperand accessor");
     SubReg = (unsigned char)subReg;
@@ -284,24 +288,13 @@ public:
   /// ChangeToImmediate - Replace this operand with a new immediate operand of
   /// the specified value.  If an operand is known to be an immediate already,
   /// the setImm method should be used.
-  void ChangeToImmediate(int64_t ImmVal) {
-    OpKind = MO_Immediate;
-    Contents.ImmVal = ImmVal;
-  }
-
+  void ChangeToImmediate(int64_t ImmVal);
+  
   /// ChangeToRegister - Replace this operand with a new register operand of
   /// the specified value.  If an operand is known to be an register already,
   /// the setReg method should be used.
   void ChangeToRegister(unsigned Reg, bool isDef, bool isImp = false,
-                        bool isKill = false, bool isDead = false) {
-    OpKind = MO_Register;
-    Contents.RegNo = Reg;
-    IsDef = isDef;
-    IsImp = isImp;
-    IsKill = isKill;
-    IsDead = isDead;
-    SubReg = 0;
-  }
+                        bool isKill = false, bool isDead = false);
   
   //===--------------------------------------------------------------------===//
   // Construction methods.
@@ -321,7 +314,9 @@ public:
     Op.IsImp = isImp;
     Op.IsKill = isKill;
     Op.IsDead = isDead;
-    Op.Contents.RegNo = Reg;
+    Op.Contents.Reg.RegNo = Reg;
+    Op.Contents.Reg.Prev = 0;
+    Op.Contents.Reg.Next = 0;
     Op.SubReg = SubReg;
     return Op;
   }
@@ -371,6 +366,37 @@ public:
   }
 
   friend class MachineInstr;
+  friend class MachineRegisterInfo;
+private:
+  //===--------------------------------------------------------------------===//
+  // Methods for handling register use/def lists.
+  //===--------------------------------------------------------------------===//
+
+  /// isOnRegUseList - Return true if this operand is on a register use/def list
+  /// or false if not.  This can only be called for register operands that are
+  /// part of a machine instruction.
+  bool isOnRegUseList() const {
+    assert(isReg() && "Can only add reg operand to use lists");
+    return Contents.Reg.Prev != 0;
+  }
+  
+  /// AddRegOperandToRegInfo - Add this register operand to the specified
+  /// MachineRegisterInfo.  If it is null, then the next/prev fields should be
+  /// explicitly nulled out.
+  void AddRegOperandToRegInfo(MachineRegisterInfo *RegInfo);
+
+  void RemoveRegOperandFromRegInfo() {
+    assert(isOnRegUseList() && "Can only add reg operand to use lists");
+    // Unlink this from the doubly linked list of operands.
+    MachineOperand *NextOp = Contents.Reg.Next;
+    *Contents.Reg.Prev = NextOp; 
+    if (NextOp) {
+      assert(NextOp->getReg() == getReg() && "Corrupt reg use/def chain!");
+      NextOp->Contents.Reg.Prev = Contents.Reg.Prev;
+    }
+    Contents.Reg.Prev = 0;
+    Contents.Reg.Next = 0;
+  }
 };
 
 inline std::ostream &operator<<(std::ostream &OS, const MachineOperand &MO) {
diff --git a/include/llvm/CodeGen/MachineRegisterInfo.h b/include/llvm/CodeGen/MachineRegisterInfo.h
index 2919d92..65eae08 100644
--- a/include/llvm/CodeGen/MachineRegisterInfo.h
+++ b/include/llvm/CodeGen/MachineRegisterInfo.h
@@ -26,7 +26,14 @@ class MachineRegisterInfo {
   /// VRegInfo - Information we keep for each virtual register.  The entries in
   /// this vector are actually converted to vreg numbers by adding the 
   /// MRegisterInfo::FirstVirtualRegister delta to their index.
-  std::vector<const TargetRegisterClass*> VRegInfo;
+  ///
+  /// Each element in this list contains the register class of the vreg and the
+  /// start of the use/def list for the register.
+  std::vector<std::pair<const TargetRegisterClass*, MachineOperand*> > VRegInfo;
+  
+  /// PhysRegUseDefLists - This is an array of the head of the use/def list for
+  /// physical registers.
+  MachineOperand **PhysRegUseDefLists; 
   
   /// UsedPhysRegs - This is a bit vector that is computed and set by the
   /// register allocator, and must be kept up to date by passes that run after
@@ -42,8 +49,21 @@ class MachineRegisterInfo {
   /// stored in the second element.
   std::vector<std::pair<unsigned, unsigned> > LiveIns;
   std::vector<unsigned> LiveOuts;
+  
+  MachineRegisterInfo(const MachineRegisterInfo&); // DO NOT IMPLEMENT
+  void operator=(const MachineRegisterInfo&);      // DO NOT IMPLEMENT
 public:
   MachineRegisterInfo(const MRegisterInfo &MRI);
+  ~MachineRegisterInfo();
+  
+  /// getRegUseDefListHead - Return the head pointer for the register use/def
+  /// list for the specified virtual or physical register.
+  MachineOperand *&getRegUseDefListHead(unsigned RegNo) {
+    if (RegNo < MRegisterInfo::FirstVirtualRegister)
+      return PhysRegUseDefLists[RegNo];
+    RegNo -= MRegisterInfo::FirstVirtualRegister;
+    return VRegInfo[RegNo].second;
+  }
   
   
   //===--------------------------------------------------------------------===//
@@ -54,15 +74,23 @@ public:
   const TargetRegisterClass *getRegClass(unsigned Reg) {
     Reg -= MRegisterInfo::FirstVirtualRegister;
     assert(Reg < VRegInfo.size() && "Invalid vreg!");
-    return VRegInfo[Reg];
+    return VRegInfo[Reg].first;
   }
-
+  
   /// createVirtualRegister - Create and return a new virtual register in the
   /// function with the specified register class.
   ///
   unsigned createVirtualRegister(const TargetRegisterClass *RegClass) {
     assert(RegClass && "Cannot create register without RegClass!");
-    VRegInfo.push_back(RegClass);
+    // Add a reg, but keep track of whether the vector reallocated or not.
+    void *ArrayBase = &VRegInfo[0];
+    VRegInfo.push_back(std::make_pair(RegClass, (MachineOperand*)0));
+    
+    if (&VRegInfo[0] == ArrayBase)
+      return getLastVirtReg();
+
+    // Otherwise, the vector reallocated, handle this now.
+    HandleVRegListReallocation();
     return getLastVirtReg();
   }
 
@@ -111,6 +139,8 @@ public:
   liveout_iterator liveout_begin() const { return LiveOuts.begin(); }
   liveout_iterator liveout_end()   const { return LiveOuts.end(); }
   bool             liveout_empty() const { return LiveOuts.empty(); }
+private:
+  void HandleVRegListReallocation();
 };
 
 } // End llvm namespace
diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp
index 3b84d68..7f93185 100644
--- a/lib/CodeGen/MachineBasicBlock.cpp
+++ b/lib/CodeGen/MachineBasicBlock.cpp
@@ -31,13 +31,23 @@ std::ostream& llvm::operator<<(std::ostream &OS, const MachineBasicBlock &MBB) {
   return OS;
 }
 
-// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
-// gets the next available unique MBB number. If it is removed from a
-// MachineFunction, it goes back to being #-1.
+/// addNodeToList (MBB) - When an MBB is added to an MF, we need to update the 
+/// parent pointer of the MBB, the MBB numbering, and any instructions in the
+/// MBB to be on the right operand list for registers.
+///
+/// MBBs start out as #-1. When a MBB is added to a MachineFunction, it
+/// gets the next available unique MBB number. If it is removed from a
+/// MachineFunction, it goes back to being #-1.
 void ilist_traits<MachineBasicBlock>::addNodeToList(MachineBasicBlock* N) {
   assert(N->getParent() == 0 && "machine instruction already in a basic block");
   N->setParent(Parent);
   N->Number = Parent->addToMBBNumbering(N);
+
+  // Make sure the instructions have their operands in the reginfo lists.
+  MachineRegisterInfo &RegInfo = Parent->getRegInfo();
+  for (MachineBasicBlock::iterator I = N->begin(), E = N->end(); I != E; ++I)
+    I->AddRegOperandsToUseLists(RegInfo);
+    
   LeakDetector::removeGarbageObject(N);
 }
 
@@ -46,6 +56,12 @@ void ilist_traits<MachineBasicBlock>::removeNodeFromList(MachineBasicBlock* N) {
   N->getParent()->removeFromMBBNumbering(N->Number);
   N->Number = -1;
   N->setParent(0);
+  
+  // Make sure the instructions have their operands removed from the reginfo
+  // lists.
+  for (MachineBasicBlock::iterator I = N->begin(), E = N->end(); I != E; ++I)
+    I->RemoveRegOperandsFromUseLists();
+  
   LeakDetector::addGarbageObject(N);
 }
 
@@ -56,27 +72,62 @@ MachineInstr* ilist_traits<MachineInstr>::createSentinel() {
   return dummy;
 }
 
+/// addNodeToList (MI) - When we add an instruction to a basic block
+/// list, we update its parent pointer and add its operands from reg use/def
+/// lists if appropriate.
 void ilist_traits<MachineInstr>::addNodeToList(MachineInstr* N) {
   assert(N->getParent() == 0 && "machine instruction already in a basic block");
   N->setParent(parent);
   LeakDetector::removeGarbageObject(N);
+  
+  // If the block is in a function, add the instruction's register operands to
+  // their corresponding use/def lists.
+  if (MachineFunction *MF = parent->getParent())
+    N->AddRegOperandsToUseLists(MF->getRegInfo());
 }
 
+/// removeNodeFromList (MI) - When we remove an instruction from a basic block
+/// list, we update its parent pointer and remove its operands from reg use/def
+/// lists if appropriate.
 void ilist_traits<MachineInstr>::removeNodeFromList(MachineInstr* N) {
   assert(N->getParent() != 0 && "machine instruction not in a basic block");
+  // If this block is in a function, remove from the use/def lists.
+  if (parent->getParent() != 0)
+    N->RemoveRegOperandsFromUseLists();
+  
   N->setParent(0);
   LeakDetector::addGarbageObject(N);
 }
 
+/// transferNodesFromList (MI) - When moving a range of instructions from one
+/// MBB list to another, we need to update the parent pointers and the use/def
+/// lists.
 void ilist_traits<MachineInstr>::transferNodesFromList(
       iplist<MachineInstr, ilist_traits<MachineInstr> >& fromList,
       ilist_iterator<MachineInstr> first,
       ilist_iterator<MachineInstr> last) {
   // Splice within the same MBB -> no change.
   if (parent == fromList.parent) return;
+
+  // If splicing between two blocks within the same function, just update the
+  // parent pointers.
+  if (parent->getParent() == fromList.parent->getParent()) {
+    for (; first != last; ++first)
+      first->setParent(parent);
+    return;
+  }
   
-  for (; first != last; ++first)
+  // Otherwise, we have to update the parent and the use/def lists.  The common
+  // case when this occurs is if we're splicing from a block in a MF to a block
+  // that is not in an MF.
+  bool HasOldMF = fromList.parent->getParent() != 0;
+  MachineFunction *NewMF = parent->getParent();
+  
+  for (; first != last; ++first) {
+    if (HasOldMF) first->RemoveRegOperandsFromUseLists();
     first->setParent(parent);
+    if (NewMF) first->AddRegOperandsToUseLists(NewMF->getRegInfo());
+  }
 }
 
 MachineBasicBlock::iterator MachineBasicBlock::getFirstTerminator() {
diff --git a/lib/CodeGen/MachineInstr.cpp b/lib/CodeGen/MachineInstr.cpp
index 4d0a98a..43cc66d 100644
--- a/lib/CodeGen/MachineInstr.cpp
+++ b/lib/CodeGen/MachineInstr.cpp
@@ -14,6 +14,7 @@
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/Value.h"
 #include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/MRegisterInfo.h"
@@ -26,6 +27,96 @@ using namespace llvm;
 // MachineOperand Implementation
 //===----------------------------------------------------------------------===//
 
+/// AddRegOperandToRegInfo - Add this register operand to the specified
+/// MachineRegisterInfo.  If it is null, then the next/prev fields should be
+/// explicitly nulled out.
+void MachineOperand::AddRegOperandToRegInfo(MachineRegisterInfo *RegInfo) {
+  assert(isReg() && "Can only add reg operand to use lists");
+  
+  // If the reginfo pointer is null, just explicitly null out or next/prev
+  // pointers, to ensure they are not garbage.
+  if (RegInfo == 0) {
+    Contents.Reg.Prev = 0;
+    Contents.Reg.Next = 0;
+    return;
+  }
+  
+  // Otherwise, add this operand to the head of the registers use/def list.
+  MachineOperand *&Head = RegInfo->getRegUseDefListHead(getReg());
+  
+  Contents.Reg.Next = Head;
+  if (Contents.Reg.Next) {
+    assert(getReg() == Contents.Reg.Next->getReg() &&
+           "Different regs on the same list!");
+    Contents.Reg.Next->Contents.Reg.Prev = &Contents.Reg.Next;
+  }
+  
+  Contents.Reg.Prev = &Head;
+  Head = this;
+}
+
+void MachineOperand::setReg(unsigned Reg) {
+  if (getReg() == Reg) return; // No change.
+  
+  // Otherwise, we have to change the register.  If this operand is embedded
+  // into a machine function, we need to update the old and new register's
+  // use/def lists.
+  if (MachineInstr *MI = getParent())
+    if (MachineBasicBlock *MBB = MI->getParent())
+      if (MachineFunction *MF = MBB->getParent()) {
+        RemoveRegOperandFromRegInfo();
+        Contents.Reg.RegNo = Reg;
+        AddRegOperandToRegInfo(&MF->getRegInfo());
+        return;
+      }
+        
+  // Otherwise, just change the register, no problem.  :)
+  Contents.Reg.RegNo = Reg;
+}
+
+/// ChangeToImmediate - Replace this operand with a new immediate operand of
+/// the specified value.  If an operand is known to be an immediate already,
+/// the setImm method should be used.
+void MachineOperand::ChangeToImmediate(int64_t ImmVal) {
+  // If this operand is currently a register operand, and if this is in a
+  // function, deregister the operand from the register's use/def list.
+  if (isReg() && getParent() && getParent()->getParent() &&
+      getParent()->getParent()->getParent())
+    RemoveRegOperandFromRegInfo();
+  
+  OpKind = MO_Immediate;
+  Contents.ImmVal = ImmVal;
+}
+
+/// ChangeToRegister - Replace this operand with a new register operand of
+/// 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) {
+  // If this operand is already a register operand, use setReg to update the 
+  // register's use/def lists.
+  if (isReg()) {
+    setReg(Reg);
+  } else {
+    // Otherwise, change this to a register and set the reg#.
+    OpKind = MO_Register;
+    Contents.Reg.RegNo = Reg;
+
+    // If this operand is embedded in a function, add the operand to the
+    // register's use/def list.
+    if (MachineInstr *MI = getParent())
+      if (MachineBasicBlock *MBB = MI->getParent())
+        if (MachineFunction *MF = MBB->getParent())
+          AddRegOperandToRegInfo(&MF->getRegInfo());
+  }
+
+  IsDef = isDef;
+  IsImp = isImp;
+  IsKill = isKill;
+  IsDead = isDead;
+  SubReg = 0;
+}
+
 /// isIdenticalTo - Return true if this operand is identical to the specified
 /// operand.
 bool MachineOperand::isIdenticalTo(const MachineOperand &Other) const {
@@ -63,8 +154,7 @@ void MachineOperand::print(std::ostream &OS, const TargetMachine *TM) const {
       OS << "%reg" << getReg();
     } else {
       // If the instruction is embedded into a basic block, we can find the
-      // target
-      // info for the instruction.
+      // target info for the instruction.
       if (TM == 0)
         if (const MachineInstr *MI = getParent())
           if (const MachineBasicBlock *MBB = MI->getParent())
@@ -212,8 +302,11 @@ MachineInstr::MachineInstr(const MachineInstr &MI) {
 MachineInstr::~MachineInstr() {
   LeakDetector::removeGarbageObject(this);
 #ifndef NDEBUG
-  for (unsigned i = 0, e = Operands.size(); i != e; ++i)
+  for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
     assert(Operands[i].ParentMI == this && "ParentMI mismatch!");
+    assert((!Operands[i].isReg() || !Operands[i].isOnRegUseList()) &&
+           "Reg operand def/use list corrupted");
+  }
 #endif
 }
 
@@ -223,6 +316,159 @@ int MachineInstr::getOpcode() const {
   return TID->Opcode;
 }
 
+/// getRegInfo - If this instruction is embedded into a MachineFunction,
+/// return the MachineRegisterInfo object for the current function, otherwise
+/// return null.
+MachineRegisterInfo *MachineInstr::getRegInfo() {
+  if (MachineBasicBlock *MBB = getParent())
+    if (MachineFunction *MF = MBB->getParent())
+      return &MF->getRegInfo();
+  return 0;
+}
+
+/// RemoveRegOperandsFromUseLists - Unlink all of the register operands in
+/// this instruction from their respective use lists.  This requires that the
+/// operands already be on their use lists.
+void MachineInstr::RemoveRegOperandsFromUseLists() {
+  for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
+    if (Operands[i].isReg())
+      Operands[i].RemoveRegOperandFromRegInfo();
+  }
+}
+
+/// AddRegOperandsToUseLists - Add all of the register operands in
+/// this instruction from their respective use lists.  This requires that the
+/// operands not be on their use lists yet.
+void MachineInstr::AddRegOperandsToUseLists(MachineRegisterInfo &RegInfo) {
+  for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
+    if (Operands[i].isReg())
+      Operands[i].AddRegOperandToRegInfo(&RegInfo);
+  }
+}
+
+
+/// addOperand - Add the specified operand to the instruction.  If it is an
+/// implicit operand, it is added to the end of the operand list.  If it is
+/// an explicit operand it is added at the end of the explicit operand list
+/// (before the first implicit operand). 
+void MachineInstr::addOperand(const MachineOperand &Op) {
+  bool isImpReg = Op.isReg() && Op.isImplicit();
+  assert((isImpReg || !OperandsComplete()) &&
+         "Trying to add an operand to a machine instr that is already done!");
+
+  // If we are adding the operand to the end of the list, our job is simpler.
+  // This is true most of the time, so this is a reasonable optimization.
+  if (isImpReg || NumImplicitOps == 0) {
+    // We can only do this optimization if we know that the operand list won't
+    // reallocate.
+    if (Operands.empty() || Operands.size()+1 <= Operands.capacity()) {
+      Operands.push_back(Op);
+    
+      // Set the parent of the operand.
+      Operands.back().ParentMI = this;
+  
+      // If the operand is a register, update the operand's use list.
+      if (Op.isReg())
+        Operands.back().AddRegOperandToRegInfo(getRegInfo());
+      return;
+    }
+  }
+  
+  // Otherwise, we have to insert a real operand before any implicit ones.
+  unsigned OpNo = Operands.size()-NumImplicitOps;
+
+  MachineRegisterInfo *RegInfo = getRegInfo();
+
+  // If this instruction isn't embedded into a function, then we don't need to
+  // update any operand lists.
+  if (RegInfo == 0) {
+    // Simple insertion, no reginfo update needed for other register operands.
+    Operands.insert(Operands.begin()+OpNo, Op);
+    Operands[OpNo].ParentMI = this;
+
+    // Do explicitly set the reginfo for this operand though, to ensure the
+    // next/prev fields are properly nulled out.
+    if (Operands[OpNo].isReg())
+      Operands[OpNo].AddRegOperandToRegInfo(0);
+
+  } else if (Operands.size()+1 <= Operands.capacity()) {
+    // Otherwise, we have to remove register operands from their register use
+    // list, add the operand, then add the register operands back to their use
+    // list.  This also must handle the case when the operand list reallocates
+    // to somewhere else.
+  
+    // If insertion of this operand won't cause reallocation of the operand
+    // list, just remove the implicit operands, add the operand, then re-add all
+    // the rest of the operands.
+    for (unsigned i = OpNo, e = Operands.size(); i != e; ++i) {
+      assert(Operands[i].isReg() && "Should only be an implicit reg!");
+      Operands[i].RemoveRegOperandFromRegInfo();
+    }
+    
+    // Add the operand.  If it is a register, add it to the reg list.
+    Operands.insert(Operands.begin()+OpNo, Op);
+    Operands[OpNo].ParentMI = this;
+
+    if (Operands[OpNo].isReg())
+      Operands[OpNo].AddRegOperandToRegInfo(RegInfo);
+    
+    // Re-add all the implicit ops.
+    for (unsigned i = OpNo+1, e = Operands.size(); i != e; ++i) {
+      assert(Operands[i].isReg() && "Should only be an implicit reg!");
+      Operands[i].AddRegOperandToRegInfo(RegInfo);
+    }
+  } else {
+    // Otherwise, we will be reallocating the operand list.  Remove all reg
+    // operands from their list, then readd them after the operand list is
+    // reallocated.
+    RemoveRegOperandsFromUseLists();
+    
+    Operands.insert(Operands.begin()+OpNo, Op);
+    Operands[OpNo].ParentMI = this;
+  
+    // Re-add all the operands.
+    AddRegOperandsToUseLists(*RegInfo);
+  }
+}
+
+/// RemoveOperand - Erase an operand  from an instruction, leaving it with one
+/// fewer operand than it started with.
+///
+void MachineInstr::RemoveOperand(unsigned OpNo) {
+  assert(OpNo < Operands.size() && "Invalid operand number");
+  
+  // Special case removing the last one.
+  if (OpNo == Operands.size()-1) {
+    // If needed, remove from the reg def/use list.
+    if (Operands.back().isReg() && Operands.back().isOnRegUseList())
+      Operands.back().RemoveRegOperandFromRegInfo();
+    
+    Operands.pop_back();
+    return;
+  }
+
+  // Otherwise, we are removing an interior operand.  If we have reginfo to
+  // update, remove all operands that will be shifted down from their reg lists,
+  // move everything down, then re-add them.
+  MachineRegisterInfo *RegInfo = getRegInfo();
+  if (RegInfo) {
+    for (unsigned i = OpNo, e = Operands.size(); i != e; ++i) {
+      if (Operands[i].isReg())
+        Operands[i].RemoveRegOperandFromRegInfo();
+    }
+  }
+  
+  Operands.erase(Operands.begin()+OpNo);
+
+  if (RegInfo) {
+    for (unsigned i = OpNo, e = Operands.size(); i != e; ++i) {
+      if (Operands[i].isReg())
+        Operands[i].AddRegOperandToRegInfo(RegInfo);
+    }
+  }
+}
+
+
 /// removeFromParent - This method unlinks 'this' from the containing basic
 /// block, and returns it, but does not delete it.
 MachineInstr *MachineInstr::removeFromParent() {
diff --git a/lib/CodeGen/MachineRegisterInfo.cpp b/lib/CodeGen/MachineRegisterInfo.cpp
index 19c09ee..f217c04 100644
--- a/lib/CodeGen/MachineRegisterInfo.cpp
+++ b/lib/CodeGen/MachineRegisterInfo.cpp
@@ -1,4 +1,4 @@
-//===-- MachineRegisterInfo.cpp -------------------------------------------===//
+//===-- lib/Codegen/MachineRegisterInfo.cpp -------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -17,4 +17,30 @@ using namespace llvm;
 MachineRegisterInfo::MachineRegisterInfo(const MRegisterInfo &MRI) {
   VRegInfo.reserve(256);
   UsedPhysRegs.resize(MRI.getNumRegs());
+  
+  // Create the physreg use/def lists.
+  PhysRegUseDefLists = new MachineOperand*[MRI.getNumRegs()];
+  memset(PhysRegUseDefLists, 0, sizeof(MachineOperand*)*MRI.getNumRegs());
+}
+
+MachineRegisterInfo::~MachineRegisterInfo() {
+#ifndef NDEBUG
+  for (unsigned i = 0, e = VRegInfo.size(); i != e; ++i)
+    assert(VRegInfo[i].second == 0 && "Vreg use list non-empty still?");
+#endif
+  delete [] PhysRegUseDefLists;
+}
+
+/// HandleVRegListReallocation - We just added a virtual register to the
+/// VRegInfo info list and it reallocated.  Update the use/def lists info
+/// pointers.
+void MachineRegisterInfo::HandleVRegListReallocation() {
+  // The back pointers for the vreg lists point into the previous vector.
+  // Update them to point to their correct slots.
+  for (unsigned i = 0, e = VRegInfo.size(); i != e; ++i) {
+    MachineOperand *List = VRegInfo[i].second;
+    if (!List) continue;
+    // Update the back-pointer to be accurate once more.
+    List->Contents.Reg.Prev = &VRegInfo[i].second;
+  }
 }