Merge commit '7dfcb84fc16b3bf6b2379713b53090757f0a45f9'

Conflicts:
	docs/LangRef.rst
	include/llvm/CodeGen/CallingConvLower.h
	include/llvm/IRReader/IRReader.h
	include/llvm/Target/TargetMachine.h
	lib/CodeGen/CallingConvLower.cpp
	lib/IRReader/IRReader.cpp
	lib/IRReader/LLVMBuild.txt
	lib/IRReader/Makefile
	lib/LLVMBuild.txt
	lib/Makefile
	lib/Support/MemoryBuffer.cpp
	lib/Support/Unix/PathV2.inc
	lib/Target/ARM/ARMBaseInstrInfo.cpp
	lib/Target/ARM/ARMISelLowering.cpp
	lib/Target/ARM/ARMInstrInfo.td
	lib/Target/ARM/ARMSubtarget.cpp
	lib/Target/ARM/ARMTargetMachine.cpp
	lib/Target/Mips/CMakeLists.txt
	lib/Target/Mips/MipsDelaySlotFiller.cpp
	lib/Target/Mips/MipsISelLowering.cpp
	lib/Target/Mips/MipsInstrInfo.td
	lib/Target/Mips/MipsSubtarget.cpp
	lib/Target/Mips/MipsSubtarget.h
	lib/Target/X86/X86FastISel.cpp
	lib/Target/X86/X86ISelDAGToDAG.cpp
	lib/Target/X86/X86ISelLowering.cpp
	lib/Target/X86/X86InstrControl.td
	lib/Target/X86/X86InstrFormats.td
	lib/Transforms/IPO/ExtractGV.cpp
	lib/Transforms/InstCombine/InstCombineCompares.cpp
	lib/Transforms/Utils/SimplifyLibCalls.cpp
	test/CodeGen/X86/fast-isel-divrem.ll
	test/MC/ARM/data-in-code.ll
	tools/Makefile
	tools/llvm-extract/llvm-extract.cpp
	tools/llvm-link/CMakeLists.txt
	tools/opt/CMakeLists.txt
	tools/opt/LLVMBuild.txt
	tools/opt/Makefile
	tools/opt/opt.cpp

1 files changed, 36 insertions, 24 deletions

diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 22b35d5271..f1b8394811 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -972,9 +972,9 @@ private:
 
   // Return the last use of reg between NewIdx and OldIdx.
   SlotIndex findLastUseBefore(unsigned Reg) {
-    SlotIndex LastUse = NewIdx;
 
     if (TargetRegisterInfo::isVirtualRegister(Reg)) {
+      SlotIndex LastUse = NewIdx;
       for (MachineRegisterInfo::use_nodbg_iterator
              UI = MRI.use_nodbg_begin(Reg),
              UE = MRI.use_nodbg_end();
@@ -984,30 +984,42 @@ private:
         if (InstSlot > LastUse && InstSlot < OldIdx)
           LastUse = InstSlot;
       }
-    } else {
-      MachineInstr* MI = LIS.getSlotIndexes()->getInstructionFromIndex(NewIdx);
-      MachineBasicBlock::iterator MII(MI);
-      ++MII;
-      MachineBasicBlock* MBB = MI->getParent();
-      for (; MII != MBB->end(); ++MII){
-        if (MII->isDebugValue())
-          continue;
-        if (LIS.getInstructionIndex(MII) < OldIdx)
-          break;
-        for (MachineInstr::mop_iterator MOI = MII->operands_begin(),
-                                        MOE = MII->operands_end();
-             MOI != MOE; ++MOI) {
-          const MachineOperand& mop = *MOI;
-          if (!mop.isReg() || mop.getReg() == 0 ||
-              TargetRegisterInfo::isVirtualRegister(mop.getReg()))
-            continue;
-
-          if (TRI.hasRegUnit(mop.getReg(), Reg))
-            LastUse = LIS.getInstructionIndex(MII);
-        }
-      }
+      return LastUse;
+    }
+
+    // This is a regunit interval, so scanning the use list could be very
+    // expensive. Scan upwards from OldIdx instead.
+    assert(NewIdx < OldIdx && "Expected upwards move");
+    SlotIndexes *Indexes = LIS.getSlotIndexes();
+    MachineBasicBlock *MBB = Indexes->getMBBFromIndex(NewIdx);
+
+    // OldIdx may not correspond to an instruction any longer, so set MII to
+    // point to the next instruction after OldIdx, or MBB->end().
+    MachineBasicBlock::iterator MII = MBB->end();
+    if (MachineInstr *MI = Indexes->getInstructionFromIndex(
+                           Indexes->getNextNonNullIndex(OldIdx)))
+      if (MI->getParent() == MBB)
+        MII = MI;
+
+    MachineBasicBlock::iterator Begin = MBB->begin();
+    while (MII != Begin) {
+      if ((--MII)->isDebugValue())
+        continue;
+      SlotIndex Idx = Indexes->getInstructionIndex(MII);
+
+      // Stop searching when NewIdx is reached.
+      if (!SlotIndex::isEarlierInstr(NewIdx, Idx))
+        return NewIdx;
+
+      // Check if MII uses Reg.
+      for (MIBundleOperands MO(MII); MO.isValid(); ++MO)
+        if (MO->isReg() &&
+            TargetRegisterInfo::isPhysicalRegister(MO->getReg()) &&
+            TRI.hasRegUnit(MO->getReg(), Reg))
+          return Idx;
     }
-    return LastUse;
+    // Didn't reach NewIdx. It must be the first instruction in the block.
+    return NewIdx;
   }
 };