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 148
