1 //===- LiveRegMatrix.h - Track register interference ----------*- C++ -*---===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // The LiveRegMatrix analysis pass keeps track of virtual register interference 10 // along two dimensions: Slot indexes and register units. The matrix is used by 11 // register allocators to ensure that no interfering virtual registers get 12 // assigned to overlapping physical registers. 13 // 14 // Register units are defined in MCRegisterInfo.h, they represent the smallest 15 // unit of interference when dealing with overlapping physical registers. The 16 // LiveRegMatrix is represented as a LiveIntervalUnion per register unit. When 17 // a virtual register is assigned to a physical register, the live range for 18 // the virtual register is inserted into the LiveIntervalUnion for each regunit 19 // in the physreg. 20 // 21 //===----------------------------------------------------------------------===// 22 23 #ifndef LLVM_CODEGEN_LIVEREGMATRIX_H 24 #define LLVM_CODEGEN_LIVEREGMATRIX_H 25 26 #include "llvm/ADT/BitVector.h" 27 #include "llvm/CodeGen/LiveIntervalUnion.h" 28 #include "llvm/CodeGen/MachineFunctionPass.h" 29 #include <memory> 30 31 namespace llvm { 32 33 class AnalysisUsage; 34 class LiveInterval; 35 class LiveIntervals; 36 class MachineFunction; 37 class TargetRegisterInfo; 38 class VirtRegMap; 39 40 class LiveRegMatrix { 41 friend class LiveRegMatrixWrapperLegacy; 42 friend class LiveRegMatrixAnalysis; 43 const TargetRegisterInfo *TRI = nullptr; 44 LiveIntervals *LIS = nullptr; 45 VirtRegMap *VRM = nullptr; 46 47 // UserTag changes whenever virtual registers have been modified. 48 unsigned UserTag = 0; 49 50 // The matrix is represented as a LiveIntervalUnion per register unit. 51 std::unique_ptr<LiveIntervalUnion::Allocator> LIUAlloc; 52 LiveIntervalUnion::Array Matrix; 53 54 // Cached queries per register unit. 55 std::unique_ptr<LiveIntervalUnion::Query[]> Queries; 56 57 // Cached register mask interference info. 58 unsigned RegMaskTag = 0; 59 unsigned RegMaskVirtReg = 0; 60 BitVector RegMaskUsable; 61 62 LiveRegMatrix() 63 : LIUAlloc(std::make_unique<LiveIntervalUnion::Allocator>()) {}; 64 void releaseMemory(); 65 66 public: 67 LiveRegMatrix(LiveRegMatrix &&Other) = default; 68 69 void init(MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM); 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(const LiveInterval &VirtReg, 109 MCRegister PhysReg); 110 111 /// Check for interference in the segment [Start, End) that may prevent 112 /// assignment to PhysReg. If this function returns true, there is 113 /// interference in the segment [Start, End) of some other interval already 114 /// assigned to PhysReg. If this function returns false, PhysReg is free at 115 /// the segment [Start, End). 116 bool checkInterference(SlotIndex Start, SlotIndex End, MCRegister PhysReg); 117 118 /// Check for interference in the segment [Start, End) that may prevent 119 /// assignment to PhysReg, like checkInterference. Returns a lane mask of 120 /// which lanes of the physical register interfere in the segment [Start, End) 121 /// of some other interval already assigned to PhysReg. 122 /// 123 /// If this function returns LaneBitmask::getNone(), PhysReg is completely 124 /// free at the segment [Start, End). 125 LaneBitmask checkInterferenceLanes(SlotIndex Start, SlotIndex End, 126 MCRegister PhysReg); 127 128 /// Assign VirtReg to PhysReg. 129 /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and 130 /// update VirtRegMap. The live range is expected to be available in PhysReg. 131 void assign(const LiveInterval &VirtReg, MCRegister PhysReg); 132 133 /// Unassign VirtReg from its PhysReg. 134 /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes 135 /// the assignment and updates VirtRegMap accordingly. 136 void unassign(const LiveInterval &VirtReg); 137 138 /// Returns true if the given \p PhysReg has any live intervals assigned. 139 bool isPhysRegUsed(MCRegister PhysReg) const; 140 141 //===--------------------------------------------------------------------===// 142 // Low-level interface. 143 //===--------------------------------------------------------------------===// 144 // 145 // Provide access to the underlying LiveIntervalUnions. 146 // 147 148 /// Check for regmask interference only. 149 /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg. 150 /// If PhysReg is null, check if VirtReg crosses any regmask operands. 151 bool checkRegMaskInterference(const LiveInterval &VirtReg, 152 MCRegister PhysReg = MCRegister::NoRegister); 153 154 /// Check for regunit interference only. 155 /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's 156 /// register units. 157 bool checkRegUnitInterference(const LiveInterval &VirtReg, 158 MCRegister PhysReg); 159 160 /// Query a line of the assigned virtual register matrix directly. 161 /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg. 162 /// This returns a reference to an internal Query data structure that is only 163 /// valid until the next query() call. 164 LiveIntervalUnion::Query &query(const LiveRange &LR, MCRegUnit RegUnit); 165 166 /// Directly access the live interval unions per regunit. 167 /// This returns an array indexed by the regunit number. 168 LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; } 169 170 Register getOneVReg(unsigned PhysReg) const; 171 }; 172 173 class LiveRegMatrixWrapperLegacy : public MachineFunctionPass { 174 LiveRegMatrix LRM; 175 176 public: 177 static char ID; 178 179 LiveRegMatrixWrapperLegacy() : MachineFunctionPass(ID) {} 180 181 LiveRegMatrix &getLRM() { return LRM; } 182 const LiveRegMatrix &getLRM() const { return LRM; } 183 184 void getAnalysisUsage(AnalysisUsage &AU) const override; 185 bool runOnMachineFunction(MachineFunction &MF) override; 186 void releaseMemory() override; 187 }; 188 189 class LiveRegMatrixAnalysis : public AnalysisInfoMixin<LiveRegMatrixAnalysis> { 190 friend AnalysisInfoMixin<LiveRegMatrixAnalysis>; 191 static AnalysisKey Key; 192 193 public: 194 using Result = LiveRegMatrix; 195 196 LiveRegMatrix run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM); 197 }; 198 199 } // end namespace llvm 200 201 #endif // LLVM_CODEGEN_LIVEREGMATRIX_H 202