Make the LiveRegMatrix analysis available to targets.

No functional change, just moved header files.

Targets can inject custom passes between register allocation and
rewriting. This makes it possible to tweak the register allocation
before rewriting, using the full global interference checking available
from LiveRegMatrix.

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

20 files changed, 21 insertions, 564 deletions

diff --git a/lib/CodeGen/AllocationOrder.cpp b/lib/CodeGen/AllocationOrder.cpp
index 7cde136c5e..96c907aa9c 100644
--- a/lib/CodeGen/AllocationOrder.cpp
+++ b/lib/CodeGen/AllocationOrder.cpp
@@ -15,9 +15,9 @@
 //===----------------------------------------------------------------------===//
 
 #include "AllocationOrder.h"
-#include "VirtRegMap.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/RegisterClassInfo.h"
+#include "llvm/CodeGen/VirtRegMap.h"
 
 using namespace llvm;
 
diff --git a/lib/CodeGen/InlineSpiller.cpp b/lib/CodeGen/InlineSpiller.cpp
index 37828a70b5..fe1db762ae 100644
--- a/lib/CodeGen/InlineSpiller.cpp
+++ b/lib/CodeGen/InlineSpiller.cpp
@@ -14,7 +14,6 @@
 
 #define DEBUG_TYPE "regalloc"
 #include "Spiller.h"
-#include "VirtRegMap.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
@@ -27,6 +26,7 @@
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Support/CommandLine.h"
diff --git a/lib/CodeGen/InterferenceCache.h b/lib/CodeGen/InterferenceCache.h
index 3c928a5086..c02fb9a1ee 100644
--- a/lib/CodeGen/InterferenceCache.h
+++ b/lib/CodeGen/InterferenceCache.h
@@ -15,7 +15,7 @@
 #ifndef LLVM_CODEGEN_INTERFERENCECACHE
 #define LLVM_CODEGEN_INTERFERENCECACHE
 
-#include "LiveIntervalUnion.h"
+#include "llvm/CodeGen/LiveIntervalUnion.h"
 
 namespace llvm {
 
diff --git a/lib/CodeGen/LiveDebugVariables.cpp b/lib/CodeGen/LiveDebugVariables.cpp
index defc1279ec..76ed35c892 100644
--- a/lib/CodeGen/LiveDebugVariables.cpp
+++ b/lib/CodeGen/LiveDebugVariables.cpp
@@ -21,7 +21,6 @@
 
 #define DEBUG_TYPE "livedebug"
 #include "LiveDebugVariables.h"
-#include "VirtRegMap.h"
 #include "llvm/Constants.h"
 #include "llvm/DebugInfo.h"
 #include "llvm/Metadata.h"
@@ -35,6 +34,7 @@
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Target/TargetInstrInfo.h"
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 4e75d892e5..c2610dc15d 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -24,6 +24,7 @@
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetMachine.h"
@@ -34,7 +35,6 @@
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "LiveRangeCalc.h"
-#include "VirtRegMap.h"
 #include <algorithm>
 #include <limits>
 #include <cmath>
diff --git a/lib/CodeGen/LiveIntervalUnion.cpp b/lib/CodeGen/LiveIntervalUnion.cpp
index 679c1807aa..430a660f2d 100644
--- a/lib/CodeGen/LiveIntervalUnion.cpp
+++ b/lib/CodeGen/LiveIntervalUnion.cpp
@@ -14,7 +14,7 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "regalloc"
-#include "LiveIntervalUnion.h"
+#include "llvm/CodeGen/LiveIntervalUnion.h"
 #include "llvm/ADT/SparseBitVector.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
diff --git a/lib/CodeGen/LiveIntervalUnion.h b/lib/CodeGen/LiveIntervalUnion.h
deleted file mode 100644
index 6a61614df4..0000000000
--- a/lib/CodeGen/LiveIntervalUnion.h
+++ /dev/null
@@ -1,205 +0,0 @@
-//===-- LiveIntervalUnion.h - Live interval union data struct --*- C++ -*--===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// LiveIntervalUnion is a union of live segments across multiple live virtual
-// registers. This may be used during coalescing to represent a congruence
-// class, or during register allocation to model liveness of a physical
-// register.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_LIVEINTERVALUNION
-#define LLVM_CODEGEN_LIVEINTERVALUNION
-
-#include "llvm/ADT/IntervalMap.h"
-#include "llvm/CodeGen/LiveInterval.h"
-
-namespace llvm {
-
-class TargetRegisterInfo;
-
-#ifndef NDEBUG
-// forward declaration
-template <unsigned Element> class SparseBitVector;
-typedef SparseBitVector<128> LiveVirtRegBitSet;
-#endif
-
-/// Compare a live virtual register segment to a LiveIntervalUnion segment.
-inline bool
-overlap(const LiveRange &VRSeg,
-        const IntervalMap<SlotIndex, LiveInterval*>::const_iterator &LUSeg) {
-  return VRSeg.start < LUSeg.stop() && LUSeg.start() < VRSeg.end;
-}
-
-/// Union of live intervals that are strong candidates for coalescing into a
-/// single register (either physical or virtual depending on the context).  We
-/// expect the constituent live intervals to be disjoint, although we may
-/// eventually make exceptions to handle value-based interference.
-class LiveIntervalUnion {
-  // A set of live virtual register segments that supports fast insertion,
-  // intersection, and removal.
-  // Mapping SlotIndex intervals to virtual register numbers.
-  typedef IntervalMap<SlotIndex, LiveInterval*> LiveSegments;
-
-public:
-  // SegmentIter can advance to the next segment ordered by starting position
-  // which may belong to a different live virtual register. We also must be able
-  // to reach the current segment's containing virtual register.
-  typedef LiveSegments::iterator SegmentIter;
-
-  // LiveIntervalUnions share an external allocator.
-  typedef LiveSegments::Allocator Allocator;
-
-  class Query;
-
-private:
-  unsigned Tag;           // unique tag for current contents.
-  LiveSegments Segments;  // union of virtual reg segments
-
-public:
-  explicit LiveIntervalUnion(Allocator &a) : Tag(0), Segments(a) {}
-
-  // Iterate over all segments in the union of live virtual registers ordered
-  // by their starting position.
-  SegmentIter begin() { return Segments.begin(); }
-  SegmentIter end() { return Segments.end(); }
-  SegmentIter find(SlotIndex x) { return Segments.find(x); }
-  bool empty() const { return Segments.empty(); }
-  SlotIndex startIndex() const { return Segments.start(); }
-
-  // Provide public access to the underlying map to allow overlap iteration.
-  typedef LiveSegments Map;
-  const Map &getMap() { return Segments; }
-
-  /// getTag - Return an opaque tag representing the current state of the union.
-  unsigned getTag() const { return Tag; }
-
-  /// changedSince - Return true if the union change since getTag returned tag.
-  bool changedSince(unsigned tag) const { return tag != Tag; }
-
-  // Add a live virtual register to this union and merge its segments.
-  void unify(LiveInterval &VirtReg);
-
-  // Remove a live virtual register's segments from this union.
-  void extract(LiveInterval &VirtReg);
-
-  // Remove all inserted virtual registers.
-  void clear() { Segments.clear(); ++Tag; }
-
-  // Print union, using TRI to translate register names
-  void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const;
-
-#ifndef NDEBUG
-  // Verify the live intervals in this union and add them to the visited set.
-  void verify(LiveVirtRegBitSet& VisitedVRegs);
-#endif
-
-  /// Query interferences between a single live virtual register and a live
-  /// interval union.
-  class Query {
-    LiveIntervalUnion *LiveUnion;
-    LiveInterval *VirtReg;
-    LiveInterval::iterator VirtRegI; // current position in VirtReg
-    SegmentIter LiveUnionI;          // current position in LiveUnion
-    SmallVector<LiveInterval*,4> InterferingVRegs;
-    bool CheckedFirstInterference;
-    bool SeenAllInterferences;
-    bool SeenUnspillableVReg;
-    unsigned Tag, UserTag;
-
-  public:
-    Query(): LiveUnion(), VirtReg(), Tag(0), UserTag(0) {}
-
-    Query(LiveInterval *VReg, LiveIntervalUnion *LIU):
-      LiveUnion(LIU), VirtReg(VReg), CheckedFirstInterference(false),
-      SeenAllInterferences(false), SeenUnspillableVReg(false)
-    {}
-
-    void clear() {
-      LiveUnion = NULL;
-      VirtReg = NULL;
-      InterferingVRegs.clear();
-      CheckedFirstInterference = false;
-      SeenAllInterferences = false;
-      SeenUnspillableVReg = false;
-      Tag = 0;
-      UserTag = 0;
-    }
-
-    void init(unsigned UTag, LiveInterval *VReg, LiveIntervalUnion *LIU) {
-      assert(VReg && LIU && "Invalid arguments");
-      if (UserTag == UTag && VirtReg == VReg &&
-          LiveUnion == LIU && !LIU->changedSince(Tag)) {
-        // Retain cached results, e.g. firstInterference.
-        return;
-      }
-      clear();
-      LiveUnion = LIU;
-      VirtReg = VReg;
-      Tag = LIU->getTag();
-      UserTag = UTag;
-    }
-
-    LiveInterval &virtReg() const {
-      assert(VirtReg && "uninitialized");
-      return *VirtReg;
-    }
-
-    // Does this live virtual register interfere with the union?
-    bool checkInterference() { return collectInterferingVRegs(1); }
-
-    // Count the virtual registers in this union that interfere with this
-    // query's live virtual register, up to maxInterferingRegs.
-    unsigned collectInterferingVRegs(unsigned MaxInterferingRegs = UINT_MAX);
-
-    // Was this virtual register visited during collectInterferingVRegs?
-    bool isSeenInterference(LiveInterval *VReg) const;
-
-    // Did collectInterferingVRegs collect all interferences?
-    bool seenAllInterferences() const { return SeenAllInterferences; }
-
-    // Did collectInterferingVRegs encounter an unspillable vreg?
-    bool seenUnspillableVReg() const { return SeenUnspillableVReg; }
-
-    // Vector generated by collectInterferingVRegs.
-    const SmallVectorImpl<LiveInterval*> &interferingVRegs() const {
-      return InterferingVRegs;
-    }
-
-  private:
-    Query(const Query&) LLVM_DELETED_FUNCTION;
-    void operator=(const Query&) LLVM_DELETED_FUNCTION;
-  };
-
-  // Array of LiveIntervalUnions.
-  class Array {
-    unsigned Size;
-    LiveIntervalUnion *LIUs;
-  public:
-    Array() : Size(0), LIUs(0) {}
-    ~Array() { clear(); }
-
-    // Initialize the array to have Size entries.
-    // Reuse an existing allocation if the size matches.
-    void init(LiveIntervalUnion::Allocator&, unsigned Size);
-
-    unsigned size() const { return Size; }
-
-    void clear();
-
-    LiveIntervalUnion& operator[](unsigned idx) {
-      assert(idx <  Size && "idx out of bounds");
-      return LIUs[idx];
-    }
-  };
-};
-
-} // end namespace llvm
-
-#endif // !defined(LLVM_CODEGEN_LIVEINTERVALUNION)
diff --git a/lib/CodeGen/LiveRangeEdit.cpp b/lib/CodeGen/LiveRangeEdit.cpp
index f8fbc7ddf0..47f9ee55a5 100644
--- a/lib/CodeGen/LiveRangeEdit.cpp
+++ b/lib/CodeGen/LiveRangeEdit.cpp
@@ -12,13 +12,13 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "regalloc"
-#include "VirtRegMap.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/CalcSpillWeights.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveRangeEdit.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
diff --git a/lib/CodeGen/LiveRegMatrix.cpp b/lib/CodeGen/LiveRegMatrix.cpp
index 7f22478d01..f0989b6b1a 100644
--- a/lib/CodeGen/LiveRegMatrix.cpp
+++ b/lib/CodeGen/LiveRegMatrix.cpp
@@ -12,12 +12,12 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "regalloc"
-#include "LiveRegMatrix.h"
 #include "RegisterCoalescer.h"
-#include "VirtRegMap.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/LiveRegMatrix.h"
+#include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Support/Debug.h"
diff --git a/lib/CodeGen/LiveRegMatrix.h b/lib/CodeGen/LiveRegMatrix.h
deleted file mode 100644
index 8f22c24478..0000000000
--- a/lib/CodeGen/LiveRegMatrix.h
+++ /dev/null
@@ -1,148 +0,0 @@
-//===-- LiveRegMatrix.h - Track register interference ---------*- C++ -*---===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// The LiveRegMatrix analysis pass keeps track of virtual register interference
-// along two dimensions: Slot indexes and register units. The matrix is used by
-// register allocators to ensure that no interfering virtual registers get
-// assigned to overlapping physical registers.
-//
-// Register units are defined in MCRegisterInfo.h, they represent the smallest
-// unit of interference when dealing with overlapping physical registers. The
-// LiveRegMatrix is represented as a LiveIntervalUnion per register unit. When
-// a virtual register is assigned to a physical register, the live range for
-// the virtual register is inserted into the LiveIntervalUnion for each regunit
-// in the physreg.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_LIVEREGMATRIX_H
-#define LLVM_CODEGEN_LIVEREGMATRIX_H
-
-#include "LiveIntervalUnion.h"
-#include "llvm/ADT/BitVector.h"
-#include "llvm/ADT/OwningPtr.h"
-#include "llvm/CodeGen/MachineFunctionPass.h"
-
-namespace llvm {
-
-class LiveInterval;
-class LiveIntervalAnalysis;
-class MachineRegisterInfo;
-class TargetRegisterInfo;
-class VirtRegMap;
-
-class LiveRegMatrix : public MachineFunctionPass {
-  const TargetRegisterInfo *TRI;
-  MachineRegisterInfo *MRI;
-  LiveIntervals *LIS;
-  VirtRegMap *VRM;
-
-  // UserTag changes whenever virtual registers have been modified.
-  unsigned UserTag;
-
-  // The matrix is represented as a LiveIntervalUnion per register unit.
-  LiveIntervalUnion::Allocator LIUAlloc;
-  LiveIntervalUnion::Array Matrix;
-
-  // Cached queries per register unit.
-  OwningArrayPtr<LiveIntervalUnion::Query> Queries;
-
-  // Cached register mask interference info.
-  unsigned RegMaskTag;
-  unsigned RegMaskVirtReg;
-  BitVector RegMaskUsable;
-
-  // MachineFunctionPass boilerplate.
-  virtual void getAnalysisUsage(AnalysisUsage&) const;
-  virtual bool runOnMachineFunction(MachineFunction&);
-  virtual void releaseMemory();
-public:
-  static char ID;
-  LiveRegMatrix();
-
-  //===--------------------------------------------------------------------===//
-  // High-level interface.
-  //===--------------------------------------------------------------------===//
-  //
-  // Check for interference before assigning virtual registers to physical
-  // registers.
-  //
-
-  /// Invalidate cached interference queries after modifying virtual register
-  /// live ranges. Interference checks may return stale information unless
-  /// caches are invalidated.
-  void invalidateVirtRegs() { ++UserTag; }
-
-  enum InterferenceKind {
-    /// No interference, go ahead and assign.
-    IK_Free = 0,
-
-    /// Virtual register interference. There are interfering virtual registers
-    /// assigned to PhysReg or its aliases. This interference could be resolved
-    /// by unassigning those other virtual registers.
-    IK_VirtReg,
-
-    /// Register unit interference. A fixed live range is in the way, typically
-    /// argument registers for a call. This can't be resolved by unassigning
-    /// other virtual registers.
-    IK_RegUnit,
-
-    /// RegMask interference. The live range is crossing an instruction with a
-    /// regmask operand that doesn't preserve PhysReg. This typically means
-    /// VirtReg is live across a call, and PhysReg isn't call-preserved.
-    IK_RegMask
-  };
-
-  /// Check for interference before assigning VirtReg to PhysReg.
-  /// If this function returns IK_Free, it is legal to assign(VirtReg, PhysReg).
-  /// When there is more than one kind of interference, the InterferenceKind
-  /// with the highest enum value is returned.
-  InterferenceKind checkInterference(LiveInterval &VirtReg, unsigned PhysReg);
-
-  /// Assign VirtReg to PhysReg.
-  /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and
-  /// update VirtRegMap. The live range is expected to be available in PhysReg.
-  void assign(LiveInterval &VirtReg, unsigned PhysReg);
-
-  /// Unassign VirtReg from its PhysReg.
-  /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes
-  /// the assignment and updates VirtRegMap accordingly.
-  void unassign(LiveInterval &VirtReg);
-
-  //===--------------------------------------------------------------------===//
-  // Low-level interface.
-  //===--------------------------------------------------------------------===//
-  //
-  // Provide access to the underlying LiveIntervalUnions.
-  //
-
-  /// Check for regmask interference only.
-  /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg.
-  /// If PhysReg is null, check if VirtReg crosses any regmask operands.
-  bool checkRegMaskInterference(LiveInterval &VirtReg, unsigned PhysReg = 0);
-
-  /// Check for regunit interference only.
-  /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's
-  /// register units.
-  bool checkRegUnitInterference(LiveInterval &VirtReg, unsigned PhysReg);
-
-  /// Query a line of the assigned virtual register matrix directly.
-  /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg.
-  /// This returns a reference to an internal Query data structure that is only
-  /// valid until the next query() call.
-  LiveIntervalUnion::Query &query(LiveInterval &VirtReg, unsigned RegUnit);
-
-  /// Directly access the live interval unions per regunit.
-  /// This returns an array indexed by the regunit number.
-  LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; }
-};
-
-} // end namespace llvm
-
-#endif // LLVM_CODEGEN_LIVEREGMATRIX_H
diff --git a/lib/CodeGen/RegAllocBase.cpp b/lib/CodeGen/RegAllocBase.cpp
index 993dbc71de..c035590357 100644
--- a/lib/CodeGen/RegAllocBase.cpp
+++ b/lib/CodeGen/RegAllocBase.cpp
@@ -14,14 +14,14 @@
 
 #define DEBUG_TYPE "regalloc"
 #include "RegAllocBase.h"
-#include "LiveRegMatrix.h"
 #include "Spiller.h"
-#include "VirtRegMap.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveRangeEdit.h"
+#include "llvm/CodeGen/LiveRegMatrix.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #ifndef NDEBUG
diff --git a/lib/CodeGen/RegAllocBase.h b/lib/CodeGen/RegAllocBase.h
index db0c8e13d3..e0e8e34358 100644
--- a/lib/CodeGen/RegAllocBase.h
+++ b/lib/CodeGen/RegAllocBase.h
@@ -37,8 +37,8 @@
 #ifndef LLVM_CODEGEN_REGALLOCBASE
 #define LLVM_CODEGEN_REGALLOCBASE
 
-#include "LiveIntervalUnion.h"
 #include "llvm/CodeGen/RegisterClassInfo.h"
+#include "llvm/CodeGen/LiveIntervalUnion.h"
 #include "llvm/ADT/OwningPtr.h"
 
 namespace llvm {
diff --git a/lib/CodeGen/RegAllocBasic.cpp b/lib/CodeGen/RegAllocBasic.cpp
index 8a49609552..1e351b6544 100644
--- a/lib/CodeGen/RegAllocBasic.cpp
+++ b/lib/CodeGen/RegAllocBasic.cpp
@@ -17,13 +17,12 @@
 #include "RegAllocBase.h"
 #include "LiveDebugVariables.h"
 #include "Spiller.h"
-#include "VirtRegMap.h"
-#include "LiveRegMatrix.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/PassAnalysisSupport.h"
 #include "llvm/CodeGen/CalcSpillWeights.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveRangeEdit.h"
+#include "llvm/CodeGen/LiveRegMatrix.h"
 #include "llvm/CodeGen/LiveStackAnalysis.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
@@ -31,6 +30,7 @@
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/RegAllocRegistry.h"
+#include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetOptions.h"
 #include "llvm/Target/TargetRegisterInfo.h"
diff --git a/lib/CodeGen/RegAllocGreedy.cpp b/lib/CodeGen/RegAllocGreedy.cpp
index 06f69c1e0d..e772379f00 100644
--- a/lib/CodeGen/RegAllocGreedy.cpp
+++ b/lib/CodeGen/RegAllocGreedy.cpp
@@ -16,12 +16,11 @@
 #include "AllocationOrder.h"
 #include "InterferenceCache.h"
 #include "LiveDebugVariables.h"
-#include "LiveRegMatrix.h"
 #include "RegAllocBase.h"
 #include "Spiller.h"
 #include "SpillPlacement.h"
 #include "SplitKit.h"
-#include "VirtRegMap.h"
+#include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/PassAnalysisSupport.h"
@@ -29,6 +28,7 @@
 #include "llvm/CodeGen/EdgeBundles.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveRangeEdit.h"
+#include "llvm/CodeGen/LiveRegMatrix.h"
 #include "llvm/CodeGen/LiveStackAnalysis.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp
index 02ebce7a11..e2110bfcd6 100644
--- a/lib/CodeGen/RegAllocPBQP.cpp
+++ b/lib/CodeGen/RegAllocPBQP.cpp
@@ -32,7 +32,6 @@
 #define DEBUG_TYPE "regalloc"
 
 #include "Spiller.h"
-#include "VirtRegMap.h"
 #include "RegisterCoalescer.h"
 #include "llvm/Module.h"
 #include "llvm/Analysis/AliasAnalysis.h"
@@ -49,6 +48,7 @@
 #include "llvm/CodeGen/PBQP/Graph.h"
 #include "llvm/CodeGen/PBQP/Heuristics/Briggs.h"
 #include "llvm/CodeGen/RegAllocRegistry.h"
+#include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
diff --git a/lib/CodeGen/RegisterCoalescer.cpp b/lib/CodeGen/RegisterCoalescer.cpp
index fcdc176581..9b52d9b126 100644
--- a/lib/CodeGen/RegisterCoalescer.cpp
+++ b/lib/CodeGen/RegisterCoalescer.cpp
@@ -16,7 +16,6 @@
 #define DEBUG_TYPE "regalloc"
 #include "RegisterCoalescer.h"
 #include "LiveDebugVariables.h"
-#include "VirtRegMap.h"
 
 #include "llvm/Pass.h"
 #include "llvm/Value.h"
@@ -33,6 +32,7 @@
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/RegisterClassInfo.h"
+#include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
diff --git a/lib/CodeGen/Spiller.cpp b/lib/CodeGen/Spiller.cpp
index 4cd22eb60f..b136860abb 100644
--- a/lib/CodeGen/Spiller.cpp
+++ b/lib/CodeGen/Spiller.cpp
@@ -10,7 +10,6 @@
 #define DEBUG_TYPE "spiller"
 
 #include "Spiller.h"
-#include "VirtRegMap.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveRangeEdit.h"
 #include "llvm/CodeGen/LiveStackAnalysis.h"
@@ -19,6 +18,7 @@
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Support/CommandLine.h"
diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp
index dca15ee758..0a3818e43f 100644
--- a/lib/CodeGen/SplitKit.cpp
+++ b/lib/CodeGen/SplitKit.cpp
@@ -14,7 +14,6 @@
 
 #define DEBUG_TYPE "regalloc"
 #include "SplitKit.h"
-#include "VirtRegMap.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveRangeEdit.h"
@@ -22,6 +21,7 @@
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/VirtRegMap.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp
index bb93bdc0bc..dc133145f6 100644
--- a/lib/CodeGen/VirtRegMap.cpp
+++ b/lib/CodeGen/VirtRegMap.cpp
@@ -17,7 +17,7 @@
 //===----------------------------------------------------------------------===//
 
 #define DEBUG_TYPE "regalloc"
-#include "VirtRegMap.h"
+#include "llvm/CodeGen/VirtRegMap.h"
 #include "LiveDebugVariables.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/LiveStackAnalysis.h"
diff --git a/lib/CodeGen/VirtRegMap.h b/lib/CodeGen/VirtRegMap.h
deleted file mode 100644
index 7974dda66a..0000000000
--- a/lib/CodeGen/VirtRegMap.h
+++ /dev/null
@@ -1,190 +0,0 @@
-//===-- llvm/CodeGen/VirtRegMap.h - Virtual Register Map -*- C++ -*--------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file implements a virtual register map. This maps virtual registers to
-// physical registers and virtual registers to stack slots. It is created and
-// updated by a register allocator and then used by a machine code rewriter that
-// adds spill code and rewrites virtual into physical register references.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_VIRTREGMAP_H
-#define LLVM_CODEGEN_VIRTREGMAP_H
-
-#include "llvm/CodeGen/MachineFunctionPass.h"
-#include "llvm/Target/TargetRegisterInfo.h"
-#include "llvm/ADT/IndexedMap.h"
-
-namespace llvm {
-  class MachineInstr;
-  class MachineFunction;
-  class MachineRegisterInfo;
-  class TargetInstrInfo;
-  class raw_ostream;
-  class SlotIndexes;
-
-  class VirtRegMap : public MachineFunctionPass {
-  public:
-    enum {
-      NO_PHYS_REG = 0,
-      NO_STACK_SLOT = (1L << 30)-1,
-      MAX_STACK_SLOT = (1L << 18)-1
-    };
-
-  private:
-    MachineRegisterInfo *MRI;
-    const TargetInstrInfo *TII;
-    const TargetRegisterInfo *TRI;
-    MachineFunction *MF;
-
-    /// Virt2PhysMap - This is a virtual to physical register
-    /// mapping. Each virtual register is required to have an entry in
-    /// it; even spilled virtual registers (the register mapped to a
-    /// spilled register is the temporary used to load it from the
-    /// stack).
-    IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2PhysMap;
-
-    /// Virt2StackSlotMap - This is virtual register to stack slot
-    /// mapping. Each spilled virtual register has an entry in it
-    /// which corresponds to the stack slot this register is spilled
-    /// at.
-    IndexedMap<int, VirtReg2IndexFunctor> Virt2StackSlotMap;
-
-    /// Virt2SplitMap - This is virtual register to splitted virtual register
-    /// mapping.
-    IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2SplitMap;
-
-    /// createSpillSlot - Allocate a spill slot for RC from MFI.
-    unsigned createSpillSlot(const TargetRegisterClass *RC);
-
-    VirtRegMap(const VirtRegMap&) LLVM_DELETED_FUNCTION;
-    void operator=(const VirtRegMap&) LLVM_DELETED_FUNCTION;
-
-  public:
-    static char ID;
-    VirtRegMap() : MachineFunctionPass(ID), Virt2PhysMap(NO_PHYS_REG),
-                   Virt2StackSlotMap(NO_STACK_SLOT), Virt2SplitMap(0) { }
-    virtual bool runOnMachineFunction(MachineFunction &MF);
-
-    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-      AU.setPreservesAll();
-      MachineFunctionPass::getAnalysisUsage(AU);
-    }
-
-    MachineFunction &getMachineFunction() const {
-      assert(MF && "getMachineFunction called before runOnMachineFunction");
-      return *MF;
-    }
-
-    MachineRegisterInfo &getRegInfo() const { return *MRI; }
-    const TargetRegisterInfo &getTargetRegInfo() const { return *TRI; }
-
-    void grow();
-
-    /// @brief returns true if the specified virtual register is
-    /// mapped to a physical register
-    bool hasPhys(unsigned virtReg) const {
-      return getPhys(virtReg) != NO_PHYS_REG;
-    }
-
-    /// @brief returns the physical register mapped to the specified
-    /// virtual register
-    unsigned getPhys(unsigned virtReg) const {
-      assert(TargetRegisterInfo::isVirtualRegister(virtReg));
-      return Virt2PhysMap[virtReg];
-    }
-
-    /// @brief creates a mapping for the specified virtual register to
-    /// the specified physical register
-    void assignVirt2Phys(unsigned virtReg, unsigned physReg) {
-      assert(TargetRegisterInfo::isVirtualRegister(virtReg) &&
-             TargetRegisterInfo::isPhysicalRegister(physReg));
-      assert(Virt2PhysMap[virtReg] == NO_PHYS_REG &&
-             "attempt to assign physical register to already mapped "
-             "virtual register");
-      Virt2PhysMap[virtReg] = physReg;
-    }
-
-    /// @brief clears the specified virtual register's, physical
-    /// register mapping
-    void clearVirt(unsigned virtReg) {
-      assert(TargetRegisterInfo::isVirtualRegister(virtReg));
-      assert(Virt2PhysMap[virtReg] != NO_PHYS_REG &&
-             "attempt to clear a not assigned virtual register");
-      Virt2PhysMap[virtReg] = NO_PHYS_REG;
-    }
-
-    /// @brief clears all virtual to physical register mappings
-    void clearAllVirt() {
-      Virt2PhysMap.clear();
-      grow();
-    }
-
-    /// @brief returns the register allocation preference.
-    unsigned getRegAllocPref(unsigned virtReg);
-
-    /// @brief returns true if VirtReg is assigned to its preferred physreg.
-    bool hasPreferredPhys(unsigned VirtReg) {
-      return getPhys(VirtReg) == getRegAllocPref(VirtReg);
-    }
-
-    /// @brief records virtReg is a split live interval from SReg.
-    void setIsSplitFromReg(unsigned virtReg, unsigned SReg) {
-      Virt2SplitMap[virtReg] = SReg;
-    }
-
-    /// @brief returns the live interval virtReg is split from.
-    unsigned getPreSplitReg(unsigned virtReg) const {
-      return Virt2SplitMap[virtReg];
-    }
-
-    /// getOriginal - Return the original virtual register that VirtReg descends
-    /// from through splitting.
-    /// A register that was not created by splitting is its own original.
-    /// This operation is idempotent.
-    unsigned getOriginal(unsigned VirtReg) const {
-      unsigned Orig = getPreSplitReg(VirtReg);
-      return Orig ? Orig : VirtReg;
-    }
-
-    /// @brief returns true if the specified virtual register is not
-    /// mapped to a stack slot or rematerialized.
-    bool isAssignedReg(unsigned virtReg) const {
-      if (getStackSlot(virtReg) == NO_STACK_SLOT)
-        return true;
-      // Split register can be assigned a physical register as well as a
-      // stack slot or remat id.
-      return (Virt2SplitMap[virtReg] && Virt2PhysMap[virtReg] != NO_PHYS_REG);
-    }
-
-    /// @brief returns the stack slot mapped to the specified virtual
-    /// register
-    int getStackSlot(unsigned virtReg) const {
-      assert(TargetRegisterInfo::isVirtualRegister(virtReg));
-      return Virt2StackSlotMap[virtReg];
-    }
-
-    /// @brief create a mapping for the specifed virtual register to
-    /// the next available stack slot
-    int assignVirt2StackSlot(unsigned virtReg);
-    /// @brief create a mapping for the specified virtual register to
-    /// the specified stack slot
-    void assignVirt2StackSlot(unsigned virtReg, int frameIndex);
-
-    void print(raw_ostream &OS, const Module* M = 0) const;
-    void dump() const;
-  };
-
-  inline raw_ostream &operator<<(raw_ostream &OS, const VirtRegMap &VRM) {
-    VRM.print(OS);
-    return OS;
-  }
-} // End llvm namespace
-
-#endif