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 /// Assign VirtReg to PhysReg. 111 /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and 112 /// update VirtRegMap. The live range is expected to be available in PhysReg. 113 void assign(LiveInterval &VirtReg, unsigned PhysReg); 114 115 /// Unassign VirtReg from its PhysReg. 116 /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes 117 /// the assignment and updates VirtRegMap accordingly. 118 void unassign(LiveInterval &VirtReg); 119 120 /// Returns true if the given \p PhysReg has any live intervals assigned. 121 bool isPhysRegUsed(unsigned PhysReg) const; 122 123 //===--------------------------------------------------------------------===// 124 // Low-level interface. 125 //===--------------------------------------------------------------------===// 126 // 127 // Provide access to the underlying LiveIntervalUnions. 128 // 129 130 /// Check for regmask interference only. 131 /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg. 132 /// If PhysReg is null, check if VirtReg crosses any regmask operands. 133 bool checkRegMaskInterference(LiveInterval &VirtReg, unsigned PhysReg = 0); 134 135 /// Check for regunit interference only. 136 /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's 137 /// register units. 138 bool checkRegUnitInterference(LiveInterval &VirtReg, unsigned PhysReg); 139 140 /// Query a line of the assigned virtual register matrix directly. 141 /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg. 142 /// This returns a reference to an internal Query data structure that is only 143 /// valid until the next query() call. 144 LiveIntervalUnion::Query &query(const LiveRange &LR, unsigned RegUnit); 145 146 /// Directly access the live interval unions per regunit. 147 /// This returns an array indexed by the regunit number. 148 LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; } 149 }; 150 151 } // end namespace llvm 152 153 #endif // LLVM_CODEGEN_LIVEREGMATRIX_H 154
