include/llvm/CodeGen/LiveRegMatrix.h

   1 //===-- LiveRegMatrix.h - Track register interference ---------*- C++ -*---===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // The LiveRegMatrix analysis pass keeps track of virtual register interference
  11 // along two dimensions: Slot indexes and register units. The matrix is used by
  12 // register allocators to ensure that no interfering virtual registers get
  13 // assigned to overlapping physical registers.
  14 //
  15 // Register units are defined in MCRegisterInfo.h, they represent the smallest
  16 // unit of interference when dealing with overlapping physical registers. The
  17 // LiveRegMatrix is represented as a LiveIntervalUnion per register unit. When
  18 // a virtual register is assigned to a physical register, the live range for
  19 // the virtual register is inserted into the LiveIntervalUnion for each regunit
  20 // in the physreg.
  21 //
  22 //===----------------------------------------------------------------------===//
  23
  24 #ifndef LLVM_CODEGEN_LIVEREGMATRIX_H
  25 #define LLVM_CODEGEN_LIVEREGMATRIX_H
  26
  27 #include "llvm/ADT/BitVector.h"
  28 #include "llvm/ADT/OwningPtr.h"
  29 #include "llvm/CodeGen/LiveIntervalUnion.h"
  30 #include "llvm/CodeGen/MachineFunctionPass.h"
  31
  32 namespace llvm {
  33
  34 class LiveInterval;
  35 class LiveIntervalAnalysis;
  36 class MachineRegisterInfo;
  37 class TargetRegisterInfo;
  38 class VirtRegMap;
  39
  40 class LiveRegMatrix : public MachineFunctionPass {
  41   const TargetRegisterInfo *TRI;
  42   MachineRegisterInfo *MRI;
  43   LiveIntervals *LIS;
  44   VirtRegMap *VRM;
  45
  46   // UserTag changes whenever virtual registers have been modified.
  47   unsigned UserTag;
  48
  49   // The matrix is represented as a LiveIntervalUnion per register unit.
  50   LiveIntervalUnion::Allocator LIUAlloc;
  51   LiveIntervalUnion::Array Matrix;
  52
  53   // Cached queries per register unit.
  54   OwningArrayPtr<LiveIntervalUnion::Query> Queries;
  55
  56   // Cached register mask interference info.
  57   unsigned RegMaskTag;
  58   unsigned RegMaskVirtReg;
  59   BitVector RegMaskUsable;
  60
  61   // MachineFunctionPass boilerplate.
  62   virtual void getAnalysisUsage(AnalysisUsage&) const;
  63   virtual bool runOnMachineFunction(MachineFunction&);
  64   virtual void releaseMemory();
  65 public:
  66   static char ID;
  67   LiveRegMatrix();
  68
  69   //===--------------------------------------------------------------------===//
  70   // High-level interface.
  71   //===--------------------------------------------------------------------===//
  72   //
  73   // Check for interference before assigning virtual registers to physical
  74   // registers.
  75   //
  76
  77   /// Invalidate cached interference queries after modifying virtual register
  78   /// live ranges. Interference checks may return stale information unless
  79   /// caches are invalidated.
  80   void invalidateVirtRegs() { ++UserTag; }
  81
  82   enum InterferenceKind {
  83     /// No interference, go ahead and assign.
  84     IK_Free = 0,
  85
  86     /// Virtual register interference. There are interfering virtual registers
  87     /// assigned to PhysReg or its aliases. This interference could be resolved
  88     /// by unassigning those other virtual registers.
  89     IK_VirtReg,
  90
  91     /// Register unit interference. A fixed live range is in the way, typically
  92     /// argument registers for a call. This can't be resolved by unassigning
  93     /// other virtual registers.
  94     IK_RegUnit,
  95
  96     /// RegMask interference. The live range is crossing an instruction with a
  97     /// regmask operand that doesn't preserve PhysReg. This typically means
  98     /// VirtReg is live across a call, and PhysReg isn't call-preserved.
  99     IK_RegMask
 100   };
 101
 102   /// Check for interference before assigning VirtReg to PhysReg.
 103   /// If this function returns IK_Free, it is legal to assign(VirtReg, PhysReg).
 104   /// When there is more than one kind of interference, the InterferenceKind
 105   /// with the highest enum value is returned.
 106   InterferenceKind checkInterference(LiveInterval &VirtReg, unsigned PhysReg);
 107
 108   /// Assign VirtReg to PhysReg.
 109   /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and
 110   /// update VirtRegMap. The live range is expected to be available in PhysReg.
 111   void assign(LiveInterval &VirtReg, unsigned PhysReg);
 112
 113   /// Unassign VirtReg from its PhysReg.
 114   /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes
 115   /// the assignment and updates VirtRegMap accordingly.
 116   void unassign(LiveInterval &VirtReg);
 117
 118   //===--------------------------------------------------------------------===//
 119   // Low-level interface.
 120   //===--------------------------------------------------------------------===//
 121   //
 122   // Provide access to the underlying LiveIntervalUnions.
 123   //
 124
 125   /// Check for regmask interference only.
 126   /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg.
 127   /// If PhysReg is null, check if VirtReg crosses any regmask operands.
 128   bool checkRegMaskInterference(LiveInterval &VirtReg, unsigned PhysReg = 0);
 129
 130   /// Check for regunit interference only.
 131   /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's
 132   /// register units.
 133   bool checkRegUnitInterference(LiveInterval &VirtReg, unsigned PhysReg);
 134
 135   /// Query a line of the assigned virtual register matrix directly.
 136   /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg.
 137   /// This returns a reference to an internal Query data structure that is only
 138   /// valid until the next query() call.
 139   LiveIntervalUnion::Query &query(LiveInterval &VirtReg, unsigned RegUnit);
 140
 141   /// Directly access the live interval unions per regunit.
 142   /// This returns an array indexed by the regunit number.
 143   LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; }
 144 };
 145
 146 } // end namespace llvm
 147
 148 #endif // LLVM_CODEGEN_LIVEREGMATRIX_H