- 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

5 files changed, 30 insertions, 106 deletions

diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index ccf7e9d4fd..1d161cf6e3 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 16899153fb..82016ed591 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 8e9933c7a7..fe78828410 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 b50a008f53..6dbc3dc299 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 480d6dd389..08f576c956 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);
           }