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/ADT/OwningPtr.h" 29 #include "llvm/CodeGen/LiveIntervalUnion.h" 30 #include "llvm/CodeGen/MachineFunctionPass.h" 31 32 namespace llvm { 33 34 class LiveInterval; 35 class LiveIntervalAnalysis; 36 class MachineRegisterInfo; 37 class TargetRegisterInfo; 38 class VirtRegMap; 39 40 class LiveRegMatrix : public MachineFunctionPass { 41 const TargetRegisterInfo *TRI; 42 MachineRegisterInfo *MRI; 43 LiveIntervals *LIS; 44 VirtRegMap *VRM; 45 46 // UserTag changes whenever virtual registers have been modified. 47 unsigned UserTag; 48 49 // The matrix is represented as a LiveIntervalUnion per register unit. 50 LiveIntervalUnion::Allocator LIUAlloc; 51 LiveIntervalUnion::Array Matrix; 52 53 // Cached queries per register unit. 54 OwningArrayPtr<LiveIntervalUnion::Query> Queries; 55 56 // Cached register mask interference info. 57 unsigned RegMaskTag; 58 unsigned RegMaskVirtReg; 59 BitVector RegMaskUsable; 60 61 // MachineFunctionPass boilerplate. 62 virtual void getAnalysisUsage(AnalysisUsage&) const; 63 virtual bool runOnMachineFunction(MachineFunction&); 64 virtual void releaseMemory(); 65 public: 66 static char ID; 67 LiveRegMatrix(); 68 69 //===--------------------------------------------------------------------===// 70 // High-level interface. 71 //===--------------------------------------------------------------------===// 72 // 73 // Check for interference before assigning virtual registers to physical 74 // registers. 75 // 76 77 /// Invalidate cached interference queries after modifying virtual register 78 /// live ranges. Interference checks may return stale information unless 79 /// caches are invalidated. 80 void invalidateVirtRegs() { ++UserTag; } 81 82 enum InterferenceKind { 83 /// No interference, go ahead and assign. 84 IK_Free = 0, 85 86 /// Virtual register interference. There are interfering virtual registers 87 /// assigned to PhysReg or its aliases. This interference could be resolved 88 /// by unassigning those other virtual registers. 89 IK_VirtReg, 90 91 /// Register unit interference. A fixed live range is in the way, typically 92 /// argument registers for a call. This can't be resolved by unassigning 93 /// other virtual registers. 94 IK_RegUnit, 95 96 /// RegMask interference. The live range is crossing an instruction with a 97 /// regmask operand that doesn't preserve PhysReg. This typically means 98 /// VirtReg is live across a call, and PhysReg isn't call-preserved. 99 IK_RegMask 100 }; 101 102 /// Check for interference before assigning VirtReg to PhysReg. 103 /// If this function returns IK_Free, it is legal to assign(VirtReg, PhysReg). 104 /// When there is more than one kind of interference, the InterferenceKind 105 /// with the highest enum value is returned. 106 InterferenceKind checkInterference(LiveInterval &VirtReg, unsigned PhysReg); 107 108 /// Assign VirtReg to PhysReg. 109 /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and 110 /// update VirtRegMap. The live range is expected to be available in PhysReg. 111 void assign(LiveInterval &VirtReg, unsigned PhysReg); 112 113 /// Unassign VirtReg from its PhysReg. 114 /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes 115 /// the assignment and updates VirtRegMap accordingly. 116 void unassign(LiveInterval &VirtReg); 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. 143 LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; } 144 }; 145 146 } // end namespace llvm 147 148 #endif // LLVM_CODEGEN_LIVEREGMATRIX_H 149
