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 : public MachineFunctionPass { 41 const TargetRegisterInfo *TRI = nullptr; 42 LiveIntervals *LIS = nullptr; 43 VirtRegMap *VRM = nullptr; 44 45 // UserTag changes whenever virtual registers have been modified. 46 unsigned UserTag = 0; 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 = 0; 57 unsigned RegMaskVirtReg = 0; 58 BitVector RegMaskUsable; 59 60 // MachineFunctionPass boilerplate. 61 void getAnalysisUsage(AnalysisUsage &) const override; 62 bool runOnMachineFunction(MachineFunction &) override; 63 void releaseMemory() override; 64 65 public: 66 static char ID; 67 68 LiveRegMatrix(); 69 70 //===--------------------------------------------------------------------===// 71 // High-level interface. 72 //===--------------------------------------------------------------------===// 73 // 74 // Check for interference before assigning virtual registers to physical 75 // registers. 76 // 77 78 /// Invalidate cached interference queries after modifying virtual register 79 /// live ranges. Interference checks may return stale information unless 80 /// caches are invalidated. invalidateVirtRegs()81 void invalidateVirtRegs() { ++UserTag; } 82 83 enum InterferenceKind { 84 /// No interference, go ahead and assign. 85 IK_Free = 0, 86 87 /// Virtual register interference. There are interfering virtual registers 88 /// assigned to PhysReg or its aliases. This interference could be resolved 89 /// by unassigning those other virtual registers. 90 IK_VirtReg, 91 92 /// Register unit interference. A fixed live range is in the way, typically 93 /// argument registers for a call. This can't be resolved by unassigning 94 /// other virtual registers. 95 IK_RegUnit, 96 97 /// RegMask interference. The live range is crossing an instruction with a 98 /// regmask operand that doesn't preserve PhysReg. This typically means 99 /// VirtReg is live across a call, and PhysReg isn't call-preserved. 100 IK_RegMask 101 }; 102 103 /// Check for interference before assigning VirtReg to PhysReg. 104 /// If this function returns IK_Free, it is legal to assign(VirtReg, PhysReg). 105 /// When there is more than one kind of interference, the InterferenceKind 106 /// with the highest enum value is returned. 107 InterferenceKind checkInterference(const LiveInterval &VirtReg, 108 MCRegister 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, MCRegister 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(const LiveInterval &VirtReg, MCRegister 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(const LiveInterval &VirtReg); 126 127 /// Returns true if the given \p PhysReg has any live intervals assigned. 128 bool isPhysRegUsed(MCRegister 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(const LiveInterval &VirtReg, 141 MCRegister PhysReg = MCRegister::NoRegister); 142 143 /// Check for regunit interference only. 144 /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's 145 /// register units. 146 bool checkRegUnitInterference(const LiveInterval &VirtReg, 147 MCRegister PhysReg); 148 149 /// Query a line of the assigned virtual register matrix directly. 150 /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg. 151 /// This returns a reference to an internal Query data structure that is only 152 /// valid until the next query() call. 153 LiveIntervalUnion::Query &query(const LiveRange &LR, MCRegister RegUnit); 154 155 /// Directly access the live interval unions per regunit. 156 /// This returns an array indexed by the regunit number. getLiveUnions()157 LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; } 158 159 Register getOneVReg(unsigned PhysReg) const; 160 }; 161 162 } // end namespace llvm 163 164 #endif // LLVM_CODEGEN_LIVEREGMATRIX_H 165