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