1 //===- LiveRegMatrix.h - Track register interference ----------*- C++ -*---===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
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
22 //===----------------------------------------------------------------------===//
24 #ifndef LLVM_CODEGEN_LIVEREGMATRIX_H
25 #define LLVM_CODEGEN_LIVEREGMATRIX_H
27 #include "llvm/ADT/BitVector.h"
28 #include "llvm/CodeGen/LiveIntervalUnion.h"
29 #include "llvm/CodeGen/MachineFunctionPass.h"
37 class MachineFunction;
38 class TargetRegisterInfo;
41 class LiveRegMatrix : public MachineFunctionPass {
42 const TargetRegisterInfo *TRI;
46 // UserTag changes whenever virtual registers have been modified.
49 // The matrix is represented as a LiveIntervalUnion per register unit.
50 LiveIntervalUnion::Allocator LIUAlloc;
51 LiveIntervalUnion::Array Matrix;
53 // Cached queries per register unit.
54 std::unique_ptr<LiveIntervalUnion::Query[]> Queries;
56 // Cached register mask interference info.
57 unsigned RegMaskTag = 0;
58 unsigned RegMaskVirtReg = 0;
59 BitVector RegMaskUsable;
61 // MachineFunctionPass boilerplate.
62 void getAnalysisUsage(AnalysisUsage &) const override;
63 bool runOnMachineFunction(MachineFunction &) override;
64 void releaseMemory() override;
71 //===--------------------------------------------------------------------===//
72 // High-level interface.
73 //===--------------------------------------------------------------------===//
75 // Check for interference before assigning virtual registers to physical
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; }
84 enum InterferenceKind {
85 /// No interference, go ahead and assign.
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.
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.
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.
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);
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);
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);
120 /// Returns true if the given \p PhysReg has any live intervals assigned.
121 bool isPhysRegUsed(unsigned PhysReg) const;
123 //===--------------------------------------------------------------------===//
124 // Low-level interface.
125 //===--------------------------------------------------------------------===//
127 // Provide access to the underlying LiveIntervalUnions.
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);
135 /// Check for regunit interference only.
136 /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's
138 bool checkRegUnitInterference(LiveInterval &VirtReg, unsigned PhysReg);
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);
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]; }
151 } // end namespace llvm
153 #endif // LLVM_CODEGEN_LIVEREGMATRIX_H