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