1249259Sdim//===-- LiveRegMatrix.h - Track register interference ---------*- C++ -*---===// 2249259Sdim// 3249259Sdim// The LLVM Compiler Infrastructure 4249259Sdim// 5249259Sdim// This file is distributed under the University of Illinois Open Source 6249259Sdim// License. See LICENSE.TXT for details. 7249259Sdim// 8249259Sdim//===----------------------------------------------------------------------===// 9249259Sdim// 10249259Sdim// The LiveRegMatrix analysis pass keeps track of virtual register interference 11249259Sdim// along two dimensions: Slot indexes and register units. The matrix is used by 12249259Sdim// register allocators to ensure that no interfering virtual registers get 13249259Sdim// assigned to overlapping physical registers. 14249259Sdim// 15249259Sdim// Register units are defined in MCRegisterInfo.h, they represent the smallest 16249259Sdim// unit of interference when dealing with overlapping physical registers. The 17249259Sdim// LiveRegMatrix is represented as a LiveIntervalUnion per register unit. When 18249259Sdim// a virtual register is assigned to a physical register, the live range for 19249259Sdim// the virtual register is inserted into the LiveIntervalUnion for each regunit 20249259Sdim// in the physreg. 21249259Sdim// 22249259Sdim//===----------------------------------------------------------------------===// 23249259Sdim 24249259Sdim#ifndef LLVM_CODEGEN_LIVEREGMATRIX_H 25249259Sdim#define LLVM_CODEGEN_LIVEREGMATRIX_H 26249259Sdim 27249259Sdim#include "llvm/ADT/BitVector.h" 28249259Sdim#include "llvm/ADT/OwningPtr.h" 29249259Sdim#include "llvm/CodeGen/LiveIntervalUnion.h" 30249259Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 31249259Sdim 32249259Sdimnamespace llvm { 33249259Sdim 34249259Sdimclass LiveInterval; 35249259Sdimclass LiveIntervalAnalysis; 36249259Sdimclass MachineRegisterInfo; 37249259Sdimclass TargetRegisterInfo; 38249259Sdimclass VirtRegMap; 39249259Sdim 40249259Sdimclass LiveRegMatrix : public MachineFunctionPass { 41249259Sdim const TargetRegisterInfo *TRI; 42249259Sdim MachineRegisterInfo *MRI; 43249259Sdim LiveIntervals *LIS; 44249259Sdim VirtRegMap *VRM; 45249259Sdim 46249259Sdim // UserTag changes whenever virtual registers have been modified. 47249259Sdim unsigned UserTag; 48249259Sdim 49249259Sdim // The matrix is represented as a LiveIntervalUnion per register unit. 50249259Sdim LiveIntervalUnion::Allocator LIUAlloc; 51249259Sdim LiveIntervalUnion::Array Matrix; 52249259Sdim 53249259Sdim // Cached queries per register unit. 54249259Sdim OwningArrayPtr<LiveIntervalUnion::Query> Queries; 55249259Sdim 56249259Sdim // Cached register mask interference info. 57249259Sdim unsigned RegMaskTag; 58249259Sdim unsigned RegMaskVirtReg; 59249259Sdim BitVector RegMaskUsable; 60249259Sdim 61249259Sdim // MachineFunctionPass boilerplate. 62249259Sdim virtual void getAnalysisUsage(AnalysisUsage&) const; 63249259Sdim virtual bool runOnMachineFunction(MachineFunction&); 64249259Sdim virtual void releaseMemory(); 65249259Sdimpublic: 66249259Sdim static char ID; 67249259Sdim LiveRegMatrix(); 68249259Sdim 69249259Sdim //===--------------------------------------------------------------------===// 70249259Sdim // High-level interface. 71249259Sdim //===--------------------------------------------------------------------===// 72249259Sdim // 73249259Sdim // Check for interference before assigning virtual registers to physical 74249259Sdim // registers. 75249259Sdim // 76249259Sdim 77249259Sdim /// Invalidate cached interference queries after modifying virtual register 78249259Sdim /// live ranges. Interference checks may return stale information unless 79249259Sdim /// caches are invalidated. 80249259Sdim void invalidateVirtRegs() { ++UserTag; } 81249259Sdim 82249259Sdim enum InterferenceKind { 83249259Sdim /// No interference, go ahead and assign. 84249259Sdim IK_Free = 0, 85249259Sdim 86249259Sdim /// Virtual register interference. There are interfering virtual registers 87249259Sdim /// assigned to PhysReg or its aliases. This interference could be resolved 88249259Sdim /// by unassigning those other virtual registers. 89249259Sdim IK_VirtReg, 90249259Sdim 91249259Sdim /// Register unit interference. A fixed live range is in the way, typically 92249259Sdim /// argument registers for a call. This can't be resolved by unassigning 93249259Sdim /// other virtual registers. 94249259Sdim IK_RegUnit, 95249259Sdim 96249259Sdim /// RegMask interference. The live range is crossing an instruction with a 97249259Sdim /// regmask operand that doesn't preserve PhysReg. This typically means 98249259Sdim /// VirtReg is live across a call, and PhysReg isn't call-preserved. 99249259Sdim IK_RegMask 100249259Sdim }; 101249259Sdim 102249259Sdim /// Check for interference before assigning VirtReg to PhysReg. 103249259Sdim /// If this function returns IK_Free, it is legal to assign(VirtReg, PhysReg). 104249259Sdim /// When there is more than one kind of interference, the InterferenceKind 105249259Sdim /// with the highest enum value is returned. 106249259Sdim InterferenceKind checkInterference(LiveInterval &VirtReg, unsigned PhysReg); 107249259Sdim 108249259Sdim /// Assign VirtReg to PhysReg. 109249259Sdim /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and 110249259Sdim /// update VirtRegMap. The live range is expected to be available in PhysReg. 111249259Sdim void assign(LiveInterval &VirtReg, unsigned PhysReg); 112249259Sdim 113249259Sdim /// Unassign VirtReg from its PhysReg. 114249259Sdim /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes 115249259Sdim /// the assignment and updates VirtRegMap accordingly. 116249259Sdim void unassign(LiveInterval &VirtReg); 117249259Sdim 118249259Sdim //===--------------------------------------------------------------------===// 119249259Sdim // Low-level interface. 120249259Sdim //===--------------------------------------------------------------------===// 121249259Sdim // 122249259Sdim // Provide access to the underlying LiveIntervalUnions. 123249259Sdim // 124249259Sdim 125249259Sdim /// Check for regmask interference only. 126249259Sdim /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg. 127249259Sdim /// If PhysReg is null, check if VirtReg crosses any regmask operands. 128249259Sdim bool checkRegMaskInterference(LiveInterval &VirtReg, unsigned PhysReg = 0); 129249259Sdim 130249259Sdim /// Check for regunit interference only. 131249259Sdim /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's 132249259Sdim /// register units. 133249259Sdim bool checkRegUnitInterference(LiveInterval &VirtReg, unsigned PhysReg); 134249259Sdim 135249259Sdim /// Query a line of the assigned virtual register matrix directly. 136249259Sdim /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg. 137249259Sdim /// This returns a reference to an internal Query data structure that is only 138249259Sdim /// valid until the next query() call. 139249259Sdim LiveIntervalUnion::Query &query(LiveInterval &VirtReg, unsigned RegUnit); 140249259Sdim 141249259Sdim /// Directly access the live interval unions per regunit. 142249259Sdim /// This returns an array indexed by the regunit number. 143249259Sdim LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; } 144249259Sdim}; 145249259Sdim 146249259Sdim} // end namespace llvm 147249259Sdim 148249259Sdim#endif // LLVM_CODEGEN_LIVEREGMATRIX_H 149