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. invalidateVirtRegs()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. getLiveUnions()143 LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; } 144 }; 145 146 } // end namespace llvm 147 148 #endif // LLVM_CODEGEN_LIVEREGMATRIX_H 149