Index: include/llvm/CodeGen/MachineBasicBlock.h
===================================================================
--- include/llvm/CodeGen/MachineBasicBlock.h
+++ include/llvm/CodeGen/MachineBasicBlock.h
@@ -14,6 +14,7 @@
 #ifndef LLVM_CODEGEN_MACHINEBASICBLOCK_H
 #define LLVM_CODEGEN_MACHINEBASICBLOCK_H
 
+#include "llvm/ADT/SortedVector.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/Support/DataTypes.h"
@@ -80,7 +81,7 @@
 
   /// LiveIns - Keep track of the physical registers that are livein of
   /// the basicblock.
-  std::vector<unsigned> LiveIns;
+  SortedVector<unsigned> LiveIns;
 
   /// Alignment - Alignment of the basic block. Zero if the basic block does
   /// not need to be aligned.
@@ -318,14 +319,18 @@
   /// Adds the specified register as a live in. Note that it is an error to add
   /// the same register to the same set more than once unless the intention is
   /// to call sortUniqueLiveIns after all registers are added.
-  void addLiveIn(unsigned Reg) { LiveIns.push_back(Reg); }
+  void addLiveIn(unsigned Reg) { LiveIns.insert(Reg); }
 
   /// Sorts and uniques the LiveIns vector. It can be significantly faster to do
   /// this than repeatedly calling isLiveIn before calling addLiveIn for every
   /// LiveIn insertion.
   void sortUniqueLiveIns() {
-    std::sort(LiveIns.begin(), LiveIns.end());
-    LiveIns.erase(std::unique(LiveIns.begin(), LiveIns.end()), LiveIns.end());
+    LiveIns.sortUnique();
+  }
+
+  /// Calls verify on the LiveIns SortedVector (verifies sorted unique order).
+  bool verifyLiveIns() const {
+    return LiveIns.verify();
   }
 
   /// Add PhysReg as live in to this block, and ensure that there is a copy of
Index: lib/CodeGen/MachineBasicBlock.cpp
===================================================================
--- lib/CodeGen/MachineBasicBlock.cpp
+++ lib/CodeGen/MachineBasicBlock.cpp
@@ -333,8 +333,7 @@
 }
 
 bool MachineBasicBlock::isLiveIn(unsigned Reg) const {
-  livein_iterator I = std::find(livein_begin(), livein_end(), Reg);
-  return I != livein_end();
+  return LiveIns.has(Reg);
 }
 
 unsigned
@@ -812,6 +811,8 @@
          E = Succ->livein_end(); I != E; ++I)
     NMBB->addLiveIn(*I);
 
+  NMBB->sortUniqueLiveIns();
+
   // Update LiveVariables.
   const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
   if (LV) {