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#include <memory> 31 32namespace llvm { 33 34class AnalysisUsage; 35class LiveInterval; 36class LiveIntervals; 37class MachineFunction; 38class TargetRegisterInfo; 39class VirtRegMap; 40 41class LiveRegMatrix : public MachineFunctionPass { 42 const TargetRegisterInfo *TRI; 43 LiveIntervals *LIS; 44 VirtRegMap *VRM; 45 46 // UserTag changes whenever virtual registers have been modified. 47 unsigned UserTag = 0; 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 std::unique_ptr<LiveIntervalUnion::Query[]> Queries; 55 56 // Cached register mask interference info. 57 unsigned RegMaskTag = 0; 58 unsigned RegMaskVirtReg = 0; 59 BitVector RegMaskUsable; 60 61 // MachineFunctionPass boilerplate. 62 void getAnalysisUsage(AnalysisUsage &) const override; 63 bool runOnMachineFunction(MachineFunction &) override; 64 void releaseMemory() override; 65 66public: 67 static char ID; 68 69 LiveRegMatrix(); 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(LiveInterval &VirtReg, unsigned PhysReg); 109 110 /// Assign VirtReg to PhysReg. 111 /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and 112 /// update VirtRegMap. The live range is expected to be available in PhysReg. 113 void assign(LiveInterval &VirtReg, unsigned PhysReg); 114 115 /// Unassign VirtReg from its PhysReg. 116 /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes 117 /// the assignment and updates VirtRegMap accordingly. 118 void unassign(LiveInterval &VirtReg); 119 120 /// Returns true if the given \p PhysReg has any live intervals assigned. 121 bool isPhysRegUsed(unsigned PhysReg) const; 122 123 //===--------------------------------------------------------------------===// 124 // Low-level interface. 125 //===--------------------------------------------------------------------===// 126 // 127 // Provide access to the underlying LiveIntervalUnions. 128 // 129 130 /// Check for regmask interference only. 131 /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg. 132 /// If PhysReg is null, check if VirtReg crosses any regmask operands. 133 bool checkRegMaskInterference(LiveInterval &VirtReg, unsigned PhysReg = 0); 134 135 /// Check for regunit interference only. 136 /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's 137 /// register units. 138 bool checkRegUnitInterference(LiveInterval &VirtReg, unsigned PhysReg); 139 140 /// Query a line of the assigned virtual register matrix directly. 141 /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg. 142 /// This returns a reference to an internal Query data structure that is only 143 /// valid until the next query() call. 144 LiveIntervalUnion::Query &query(const LiveRange &LR, unsigned RegUnit); 145 146 /// Directly access the live interval unions per regunit. 147 /// This returns an array indexed by the regunit number. 148 LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; } 149}; 150 151} // end namespace llvm 152 153#endif // LLVM_CODEGEN_LIVEREGMATRIX_H 154