180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru//===-- LiveRegMatrix.h - Track register interference ---------*- C++ -*---===// 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// The LLVM Compiler Infrastructure 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// This file is distributed under the University of Illinois Open Source 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// License. See LICENSE.TXT for details. 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru//===----------------------------------------------------------------------===// 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// The LiveRegMatrix analysis pass keeps track of virtual register interference 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// along two dimensions: Slot indexes and register units. The matrix is used by 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru// 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 31namespace llvm { 32 33class LiveInterval; 34class LiveIntervalAnalysis; 35class MachineRegisterInfo; 36class TargetRegisterInfo; 37class VirtRegMap; 38 39class LiveRegMatrix : public MachineFunctionPass { 40 const TargetRegisterInfo *TRI; 41 MachineRegisterInfo *MRI; 42 LiveIntervals *LIS; 43 VirtRegMap *VRM; 44 45 // UserTag changes whenever virtual registers have been modified. 46 unsigned UserTag; 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; 57 unsigned RegMaskVirtReg; 58 BitVector RegMaskUsable; 59 60 // MachineFunctionPass boilerplate. 61 void getAnalysisUsage(AnalysisUsage&) const override; 62 bool runOnMachineFunction(MachineFunction&) override; 63 void releaseMemory() override; 64public: 65 static char ID; 66 LiveRegMatrix(); 67 68 //===--------------------------------------------------------------------===// 69 // High-level interface. 70 //===--------------------------------------------------------------------===// 71 // 72 // Check for interference before assigning virtual registers to physical 73 // registers. 74 // 75 76 /// Invalidate cached interference queries after modifying virtual register 77 /// live ranges. Interference checks may return stale information unless 78 /// caches are invalidated. 79 void invalidateVirtRegs() { ++UserTag; } 80 81 enum InterferenceKind { 82 /// No interference, go ahead and assign. 83 IK_Free = 0, 84 85 /// Virtual register interference. There are interfering virtual registers 86 /// assigned to PhysReg or its aliases. This interference could be resolved 87 /// by unassigning those other virtual registers. 88 IK_VirtReg, 89 90 /// Register unit interference. A fixed live range is in the way, typically 91 /// argument registers for a call. This can't be resolved by unassigning 92 /// other virtual registers. 93 IK_RegUnit, 94 95 /// RegMask interference. The live range is crossing an instruction with a 96 /// regmask operand that doesn't preserve PhysReg. This typically means 97 /// VirtReg is live across a call, and PhysReg isn't call-preserved. 98 IK_RegMask 99 }; 100 101 /// Check for interference before assigning VirtReg to PhysReg. 102 /// If this function returns IK_Free, it is legal to assign(VirtReg, PhysReg). 103 /// When there is more than one kind of interference, the InterferenceKind 104 /// with the highest enum value is returned. 105 InterferenceKind checkInterference(LiveInterval &VirtReg, unsigned PhysReg); 106 107 /// Assign VirtReg to PhysReg. 108 /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and 109 /// update VirtRegMap. The live range is expected to be available in PhysReg. 110 void assign(LiveInterval &VirtReg, unsigned PhysReg); 111 112 /// Unassign VirtReg from its PhysReg. 113 /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes 114 /// the assignment and updates VirtRegMap accordingly. 115 void unassign(LiveInterval &VirtReg); 116 117 //===--------------------------------------------------------------------===// 118 // Low-level interface. 119 //===--------------------------------------------------------------------===// 120 // 121 // Provide access to the underlying LiveIntervalUnions. 122 // 123 124 /// Check for regmask interference only. 125 /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg. 126 /// If PhysReg is null, check if VirtReg crosses any regmask operands. 127 bool checkRegMaskInterference(LiveInterval &VirtReg, unsigned PhysReg = 0); 128 129 /// Check for regunit interference only. 130 /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's 131 /// register units. 132 bool checkRegUnitInterference(LiveInterval &VirtReg, unsigned PhysReg); 133 134 /// Query a line of the assigned virtual register matrix directly. 135 /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg. 136 /// This returns a reference to an internal Query data structure that is only 137 /// valid until the next query() call. 138 LiveIntervalUnion::Query &query(LiveInterval &VirtReg, unsigned RegUnit); 139 140 /// Directly access the live interval unions per regunit. 141 /// This returns an array indexed by the regunit number. 142 LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; } 143}; 144 145} // end namespace llvm 146 147#endif // LLVM_CODEGEN_LIVEREGMATRIX_H 148