Teach TransferDeadness to delete truly dead instructions if they do not produce side effects.

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

2 files changed, 60 insertions, 21 deletions

diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index 2c30bd81c6..c5ce455b0a 100644
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -350,29 +350,44 @@ unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) {
   if (!vni->def || vni->def == ~1U || vni->def == ~0U)
     return Reg;
   MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
-  unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
+  unsigned SrcReg, DstReg, SrcSubReg, DstSubReg, PhysReg;
   if (!CopyMI ||
       !tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg))
     return Reg;
+  PhysReg = SrcReg;
   if (TargetRegisterInfo::isVirtualRegister(SrcReg)) {
     if (!vrm_->isAssignedReg(SrcReg))
       return Reg;
-    else
-      SrcReg = vrm_->getPhys(SrcReg);
+    PhysReg = vrm_->getPhys(SrcReg);
   }
-  if (Reg == SrcReg)
+  if (Reg == PhysReg)
     return Reg;
 
   const TargetRegisterClass *RC = mri_->getRegClass(cur.reg);
-  if (!RC->contains(SrcReg))
+  if (!RC->contains(PhysReg))
     return Reg;
 
   // Try to coalesce.
-  if (!li_->conflictsWithPhysRegDef(cur, *vrm_, SrcReg)) {
-    DOUT << "Coalescing: " << cur << " -> " << tri_->getName(SrcReg)
+  if (!li_->conflictsWithPhysRegDef(cur, *vrm_, PhysReg)) {
+    DOUT << "Coalescing: " << cur << " -> " << tri_->getName(PhysReg)
          << '\n';
     vrm_->clearVirt(cur.reg);
-    vrm_->assignVirt2Phys(cur.reg, SrcReg);
+    vrm_->assignVirt2Phys(cur.reg, PhysReg);
+
+    // Remove unnecessary kills since a copy does not clobber the register.
+    if (li_->hasInterval(SrcReg)) {
+      LiveInterval &SrcLI = li_->getInterval(SrcReg);
+      for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(cur.reg),
+             E = mri_->reg_end(); I != E; ++I) {
+        MachineOperand &O = I.getOperand();
+        if (!O.isUse() || !O.isKill())
+          continue;
+        MachineInstr *MI = &*I;
+        if (SrcLI.liveAt(li_->getDefIndex(li_->getInstructionIndex(MI))))
+          O.setIsKill(false);
+      }
+    }
+
     ++NumCoalesce;
     return SrcReg;
   }
diff --git a/lib/CodeGen/VirtRegRewriter.cpp b/lib/CodeGen/VirtRegRewriter.cpp
index 025ce1bd30..3cbecf4a0d 100644
--- a/lib/CodeGen/VirtRegRewriter.cpp
+++ b/lib/CodeGen/VirtRegRewriter.cpp
@@ -851,6 +851,14 @@ void AssignPhysToVirtReg(MachineInstr *MI, unsigned VirtReg, unsigned PhysReg) {
   }
 }
 
+namespace {
+  struct RefSorter {
+    bool operator()(const std::pair<MachineInstr*, int> &A,
+                    const std::pair<MachineInstr*, int> &B) {
+      return A.second < B.second;
+    }
+  };
+}
 
 // ***************************** //
 // Local Spiller Implementation  //
@@ -1313,9 +1321,10 @@ private:
   /// removed. Find the last def or use and mark it as dead / kill.
   void TransferDeadness(MachineBasicBlock *MBB, unsigned CurDist,
                         unsigned Reg, BitVector &RegKills,
-                        std::vector<MachineOperand*> &KillOps) {
-    int LastUDDist = -1;
-    MachineInstr *LastUDMI = NULL;
+                        std::vector<MachineOperand*> &KillOps,
+                        VirtRegMap &VRM) {
+    SmallPtrSet<MachineInstr*, 4> Seens;
+    SmallVector<std::pair<MachineInstr*, int>,8> Refs;
     for (MachineRegisterInfo::reg_iterator RI = RegInfo->reg_begin(Reg),
            RE = RegInfo->reg_end(); RI != RE; ++RI) {
       MachineInstr *UDMI = &*RI;
@@ -1324,13 +1333,18 @@ private:
       DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI);
       if (DI == DistanceMap.end() || DI->second > CurDist)
         continue;
-      if ((int)DI->second < LastUDDist)
-        continue;
-      LastUDDist = DI->second;
-      LastUDMI = UDMI;
+      if (Seens.insert(UDMI))
+        Refs.push_back(std::make_pair(UDMI, DI->second));
     }
 
-    if (LastUDMI) {
+    if (Refs.empty())
+      return;
+    std::sort(Refs.begin(), Refs.end(), RefSorter());
+
+    while (!Refs.empty()) {
+      MachineInstr *LastUDMI = Refs.back().first;
+      Refs.pop_back();
+
       MachineOperand *LastUD = NULL;
       for (unsigned i = 0, e = LastUDMI->getNumOperands(); i != e; ++i) {
         MachineOperand &MO = LastUDMI->getOperand(i);
@@ -1339,14 +1353,24 @@ private:
         if (!LastUD || (LastUD->isUse() && MO.isDef()))
           LastUD = &MO;
         if (LastUDMI->isRegTiedToDefOperand(i))
-          return;
+          break;
       }
-      if (LastUD->isDef())
-        LastUD->setIsDead();
-      else {
+      if (LastUD->isDef()) {
+        // If the instruction has no side effect, delete it and propagate
+        // backward further. Otherwise, mark is dead and we are done.
+        const TargetInstrDesc &TID = LastUDMI->getDesc();
+        if (TID.mayStore() || TID.isCall() || TID.isTerminator() ||
+            TID.hasUnmodeledSideEffects()) {
+          LastUD->setIsDead();
+          break;
+        }
+        VRM.RemoveMachineInstrFromMaps(LastUDMI);
+        MBB->erase(LastUDMI);
+      } else {
         LastUD->setIsKill();
         RegKills.set(Reg);
         KillOps[Reg] = LastUD;
+        break;
       }
     }
   }
@@ -2027,7 +2051,7 @@ private:
                      TRI->isSubRegister(KillRegs[0], Dst) ||
                      TRI->isSuperRegister(KillRegs[0], Dst));
               // Last def is now dead.
-              TransferDeadness(&MBB, Dist, Src, RegKills, KillOps);
+              TransferDeadness(&MBB, Dist, Src, RegKills, KillOps, VRM);
             }
             VRM.RemoveMachineInstrFromMaps(&MI);
             MBB.erase(&MI);