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