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 TargetRegisterInfo;
  36 class VirtRegMap;
  37
  38 class LiveRegMatrix : public MachineFunctionPass {
  39   const TargetRegisterInfo *TRI;
  40   LiveIntervals *LIS;
  41   VirtRegMap *VRM;
  42
  43   // UserTag changes whenever virtual registers have been modified.
  44   unsigned UserTag;
  45
  46   // The matrix is represented as a LiveIntervalUnion per register unit.
  47   LiveIntervalUnion::Allocator LIUAlloc;
  48   LiveIntervalUnion::Array Matrix;
  49
  50   // Cached queries per register unit.
  51   std::unique_ptr<LiveIntervalUnion::Query[]> Queries;
  52
  53   // Cached register mask interference info.
  54   unsigned RegMaskTag;
  55   unsigned RegMaskVirtReg;
  56   BitVector RegMaskUsable;
  57
  58   // MachineFunctionPass boilerplate.
  59   void getAnalysisUsage(AnalysisUsage&) const override;
  60   bool runOnMachineFunction(MachineFunction&) override;
  61   void releaseMemory() override;
  62 public:
  63   static char ID;
  64   LiveRegMatrix();
  65
  66   //===--------------------------------------------------------------------===//
  67   // High-level interface.
  68   //===--------------------------------------------------------------------===//
  69   //
  70   // Check for interference before assigning virtual registers to physical
  71   // registers.
  72   //
  73
  74   /// Invalidate cached interference queries after modifying virtual register
  75   /// live ranges. Interference checks may return stale information unless
  76   /// caches are invalidated.
  77   void invalidateVirtRegs() { ++UserTag; }
  78
  79   enum InterferenceKind {
  80     /// No interference, go ahead and assign.
  81     IK_Free = 0,
  82
  83     /// Virtual register interference. There are interfering virtual registers
  84     /// assigned to PhysReg or its aliases. This interference could be resolved
  85     /// by unassigning those other virtual registers.
  86     IK_VirtReg,
  87
  88     /// Register unit interference. A fixed live range is in the way, typically
  89     /// argument registers for a call. This can't be resolved by unassigning
  90     /// other virtual registers.
  91     IK_RegUnit,
  92
  93     /// RegMask interference. The live range is crossing an instruction with a
  94     /// regmask operand that doesn't preserve PhysReg. This typically means
  95     /// VirtReg is live across a call, and PhysReg isn't call-preserved.
  96     IK_RegMask
  97   };
  98
  99   /// Check for interference before assigning VirtReg to PhysReg.
 100   /// If this function returns IK_Free, it is legal to assign(VirtReg, PhysReg).
 101   /// When there is more than one kind of interference, the InterferenceKind
 102   /// with the highest enum value is returned.
 103   InterferenceKind checkInterference(LiveInterval &VirtReg, unsigned PhysReg);
 104
 105   /// Assign VirtReg to PhysReg.
 106   /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and
 107   /// update VirtRegMap. The live range is expected to be available in PhysReg.
 108   void assign(LiveInterval &VirtReg, unsigned PhysReg);
 109
 110   /// Unassign VirtReg from its PhysReg.
 111   /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes
 112   /// the assignment and updates VirtRegMap accordingly.
 113   void unassign(LiveInterval &VirtReg);
 114
 115   /// Returns true if the given \p PhysReg has any live intervals assigned.
 116   bool isPhysRegUsed(unsigned PhysReg) const;
 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