Merge commit '10251753b6897adcd22cc981c0cc42f348c109de' into merge-20130807

Conflicts:
	lib/Archive/ArchiveReader.cpp
	lib/Support/Unix/PathV2.inc

Change-Id: I29d8c1e321a4a380b6013f00bac6a8e4b593cc4e

1 files changed, 113 insertions, 98 deletions

diff --git a/lib/CodeGen/LiveRangeEdit.cpp b/lib/CodeGen/LiveRangeEdit.cpp
index 7793e96..792ef54 100644
--- a/lib/CodeGen/LiveRangeEdit.cpp
+++ b/lib/CodeGen/LiveRangeEdit.cpp
@@ -13,7 +13,6 @@
 
 #define DEBUG_TYPE "regalloc"
 #include "llvm/CodeGen/LiveRangeEdit.h"
-#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/CalcSpillWeights.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
@@ -216,108 +215,122 @@ bool LiveRangeEdit::foldAsLoad(LiveInterval *LI,
   return true;
 }
 
-void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr*> &Dead,
-                                      ArrayRef<unsigned> RegsBeingSpilled) {
-  SetVector<LiveInterval*,
-            SmallVector<LiveInterval*, 8>,
-            SmallPtrSet<LiveInterval*, 8> > ToShrink;
+/// Find all live intervals that need to shrink, then remove the instruction.
+void LiveRangeEdit::eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink) {
+  assert(MI->allDefsAreDead() && "Def isn't really dead");
+  SlotIndex Idx = LIS.getInstructionIndex(MI).getRegSlot();
 
-  for (;;) {
-    // Erase all dead defs.
-    while (!Dead.empty()) {
-      MachineInstr *MI = Dead.pop_back_val();
-      assert(MI->allDefsAreDead() && "Def isn't really dead");
-      SlotIndex Idx = LIS.getInstructionIndex(MI).getRegSlot();
-
-      // Never delete inline asm.
-      if (MI->isInlineAsm()) {
-        DEBUG(dbgs() << "Won't delete: " << Idx << '\t' << *MI);
-        continue;
-      }
+  // Never delete a bundled instruction.
+  if (MI->isBundled()) {
+    return;
+  }
+  // Never delete inline asm.
+  if (MI->isInlineAsm()) {
+    DEBUG(dbgs() << "Won't delete: " << Idx << '\t' << *MI);
+    return;
+  }
 
-      // Use the same criteria as DeadMachineInstructionElim.
-      bool SawStore = false;
-      if (!MI->isSafeToMove(&TII, 0, SawStore)) {
-        DEBUG(dbgs() << "Can't delete: " << Idx << '\t' << *MI);
-        continue;
-      }
+  // Use the same criteria as DeadMachineInstructionElim.
+  bool SawStore = false;
+  if (!MI->isSafeToMove(&TII, 0, SawStore)) {
+    DEBUG(dbgs() << "Can't delete: " << Idx << '\t' << *MI);
+    return;
+  }
 
-      DEBUG(dbgs() << "Deleting dead def " << Idx << '\t' << *MI);
-
-      // Collect virtual registers to be erased after MI is gone.
-      SmallVector<unsigned, 8> RegsToErase;
-      bool ReadsPhysRegs = false;
-
-      // Check for live intervals that may shrink
-      for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
-             MOE = MI->operands_end(); MOI != MOE; ++MOI) {
-        if (!MOI->isReg())
-          continue;
-        unsigned Reg = MOI->getReg();
-        if (!TargetRegisterInfo::isVirtualRegister(Reg)) {
-          // Check if MI reads any unreserved physregs.
-          if (Reg && MOI->readsReg() && !MRI.isReserved(Reg))
-            ReadsPhysRegs = true;
-          continue;
-        }
-        LiveInterval &LI = LIS.getInterval(Reg);
-
-        // Shrink read registers, unless it is likely to be expensive and
-        // unlikely to change anything. We typically don't want to shrink the
-        // PIC base register that has lots of uses everywhere.
-        // Always shrink COPY uses that probably come from live range splitting.
-        if (MI->readsVirtualRegister(Reg) &&
-            (MI->isCopy() || MOI->isDef() || MRI.hasOneNonDBGUse(Reg) ||
-             LI.killedAt(Idx)))
-          ToShrink.insert(&LI);
-
-        // Remove defined value.
-        if (MOI->isDef()) {
-          if (VNInfo *VNI = LI.getVNInfoAt(Idx)) {
-            if (TheDelegate)
-              TheDelegate->LRE_WillShrinkVirtReg(LI.reg);
-            LI.removeValNo(VNI);
-            if (LI.empty())
-              RegsToErase.push_back(Reg);
+  DEBUG(dbgs() << "Deleting dead def " << Idx << '\t' << *MI);
+
+  // Collect virtual registers to be erased after MI is gone.
+  SmallVector<unsigned, 8> RegsToErase;
+  bool ReadsPhysRegs = false;
+
+  // Check for live intervals that may shrink
+  for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
+         MOE = MI->operands_end(); MOI != MOE; ++MOI) {
+    if (!MOI->isReg())
+      continue;
+    unsigned Reg = MOI->getReg();
+    if (!TargetRegisterInfo::isVirtualRegister(Reg)) {
+      // Check if MI reads any unreserved physregs.
+      if (Reg && MOI->readsReg() && !MRI.isReserved(Reg))
+        ReadsPhysRegs = true;
+      else if (MOI->isDef()) {
+        for (MCRegUnitIterator Units(Reg, MRI.getTargetRegisterInfo());
+             Units.isValid(); ++Units) {
+          if (LiveInterval *LI = LIS.getCachedRegUnit(*Units)) {
+            if (VNInfo *VNI = LI->getVNInfoAt(Idx))
+              LI->removeValNo(VNI);
           }
         }
       }
-
-      // Currently, we don't support DCE of physreg live ranges. If MI reads
-      // any unreserved physregs, don't erase the instruction, but turn it into
-      // a KILL instead. This way, the physreg live ranges don't end up
-      // dangling.
-      // FIXME: It would be better to have something like shrinkToUses() for
-      // physregs. That could potentially enable more DCE and it would free up
-      // the physreg. It would not happen often, though.
-      if (ReadsPhysRegs) {
-        MI->setDesc(TII.get(TargetOpcode::KILL));
-        // Remove all operands that aren't physregs.
-        for (unsigned i = MI->getNumOperands(); i; --i) {
-          const MachineOperand &MO = MI->getOperand(i-1);
-          if (MO.isReg() && TargetRegisterInfo::isPhysicalRegister(MO.getReg()))
-            continue;
-          MI->RemoveOperand(i-1);
-        }
-        DEBUG(dbgs() << "Converted physregs to:\t" << *MI);
-      } else {
+      continue;
+    }
+    LiveInterval &LI = LIS.getInterval(Reg);
+
+    // Shrink read registers, unless it is likely to be expensive and
+    // unlikely to change anything. We typically don't want to shrink the
+    // PIC base register that has lots of uses everywhere.
+    // Always shrink COPY uses that probably come from live range splitting.
+    if (MI->readsVirtualRegister(Reg) &&
+        (MI->isCopy() || MOI->isDef() || MRI.hasOneNonDBGUse(Reg) ||
+         LI.killedAt(Idx)))
+      ToShrink.insert(&LI);
+
+    // Remove defined value.
+    if (MOI->isDef()) {
+      if (VNInfo *VNI = LI.getVNInfoAt(Idx)) {
         if (TheDelegate)
-          TheDelegate->LRE_WillEraseInstruction(MI);
-        LIS.RemoveMachineInstrFromMaps(MI);
-        MI->eraseFromParent();
-        ++NumDCEDeleted;
+          TheDelegate->LRE_WillShrinkVirtReg(LI.reg);
+        LI.removeValNo(VNI);
+        if (LI.empty())
+          RegsToErase.push_back(Reg);
       }
+    }
+  }
 
-      // Erase any virtregs that are now empty and unused. There may be <undef>
-      // uses around. Keep the empty live range in that case.
-      for (unsigned i = 0, e = RegsToErase.size(); i != e; ++i) {
-        unsigned Reg = RegsToErase[i];
-        if (LIS.hasInterval(Reg) && MRI.reg_nodbg_empty(Reg)) {
-          ToShrink.remove(&LIS.getInterval(Reg));
-          eraseVirtReg(Reg);
-        }
-      }
+  // Currently, we don't support DCE of physreg live ranges. If MI reads
+  // any unreserved physregs, don't erase the instruction, but turn it into
+  // a KILL instead. This way, the physreg live ranges don't end up
+  // dangling.
+  // FIXME: It would be better to have something like shrinkToUses() for
+  // physregs. That could potentially enable more DCE and it would free up
+  // the physreg. It would not happen often, though.
+  if (ReadsPhysRegs) {
+    MI->setDesc(TII.get(TargetOpcode::KILL));
+    // Remove all operands that aren't physregs.
+    for (unsigned i = MI->getNumOperands(); i; --i) {
+      const MachineOperand &MO = MI->getOperand(i-1);
+      if (MO.isReg() && TargetRegisterInfo::isPhysicalRegister(MO.getReg()))
+        continue;
+      MI->RemoveOperand(i-1);
     }
+    DEBUG(dbgs() << "Converted physregs to:\t" << *MI);
+  } else {
+    if (TheDelegate)
+      TheDelegate->LRE_WillEraseInstruction(MI);
+    LIS.RemoveMachineInstrFromMaps(MI);
+    MI->eraseFromParent();
+    ++NumDCEDeleted;
+  }
+
+  // Erase any virtregs that are now empty and unused. There may be <undef>
+  // uses around. Keep the empty live range in that case.
+  for (unsigned i = 0, e = RegsToErase.size(); i != e; ++i) {
+    unsigned Reg = RegsToErase[i];
+    if (LIS.hasInterval(Reg) && MRI.reg_nodbg_empty(Reg)) {
+      ToShrink.remove(&LIS.getInterval(Reg));
+      eraseVirtReg(Reg);
+    }
+  }
+}
+
+void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr*> &Dead,
+                                      ArrayRef<unsigned> RegsBeingSpilled) {
+  ToShrinkSet ToShrink;
+
+  for (;;) {
+    // Erase all dead defs.
+    while (!Dead.empty())
+      eliminateDeadDef(Dead.pop_back_val(), ToShrink);
 
     if (ToShrink.empty())
       break;
@@ -331,7 +344,7 @@ void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr*> &Dead,
       TheDelegate->LRE_WillShrinkVirtReg(LI->reg);
     if (!LIS.shrinkToUses(LI, &Dead))
       continue;
-    
+
     // Don't create new intervals for a register being spilled.
     // The new intervals would have to be spilled anyway so its not worth it.
     // Also they currently aren't spilled so creating them and not spilling
@@ -343,7 +356,7 @@ void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr*> &Dead,
         break;
       }
     }
-    
+
     if (BeingSpilled) continue;
 
     // LI may have been separated, create new intervals.
@@ -374,9 +387,11 @@ void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr*> &Dead,
   }
 }
 
-void LiveRangeEdit::calculateRegClassAndHint(MachineFunction &MF,
-                                             const MachineLoopInfo &Loops) {
-  VirtRegAuxInfo VRAI(MF, LIS, Loops);
+void
+LiveRangeEdit::calculateRegClassAndHint(MachineFunction &MF,
+                                        const MachineLoopInfo &Loops,
+                                        const MachineBlockFrequencyInfo &MBFI) {
+  VirtRegAuxInfo VRAI(MF, LIS, Loops, MBFI);
   for (iterator I = begin(), E = end(); I != E; ++I) {
     LiveInterval &LI = **I;
     if (MRI.recomputeRegClass(LI.reg, MF.getTarget()))