1//===- LiveRegMatrix.h - Track register interference ----------*- C++ -*---===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// The LiveRegMatrix analysis pass keeps track of virtual register interference
10// along two dimensions: Slot indexes and register units. The matrix is used by
11// register allocators to ensure that no interfering virtual registers get
12// assigned to overlapping physical registers.
13//
14// Register units are defined in MCRegisterInfo.h, they represent the smallest
15// unit of interference when dealing with overlapping physical registers. The
16// LiveRegMatrix is represented as a LiveIntervalUnion per register unit. When
17// a virtual register is assigned to a physical register, the live range for
18// the virtual register is inserted into the LiveIntervalUnion for each regunit
19// in the physreg.
20//
21//===----------------------------------------------------------------------===//
22
23#ifndef LLVM_CODEGEN_LIVEREGMATRIX_H
24#define LLVM_CODEGEN_LIVEREGMATRIX_H
25
26#include "llvm/ADT/BitVector.h"
27#include "llvm/CodeGen/LiveIntervalUnion.h"
28#include "llvm/CodeGen/MachineFunctionPass.h"
29#include <memory>
30
31namespace llvm {
32
33class AnalysisUsage;
34class LiveInterval;
35class LiveIntervals;
36class MachineFunction;
37class TargetRegisterInfo;
38class VirtRegMap;
39
40class LiveRegMatrix {
41 friend class LiveRegMatrixWrapperLegacy;
42 friend class LiveRegMatrixAnalysis;
43 const TargetRegisterInfo *TRI = nullptr;
44 LiveIntervals *LIS = nullptr;
45 VirtRegMap *VRM = nullptr;
46
47 // UserTag changes whenever virtual registers have been modified.
48 unsigned UserTag = 0;
49
50 // The matrix is represented as a LiveIntervalUnion per register unit.
51 std::unique_ptr<LiveIntervalUnion::Allocator> LIUAlloc;
52 LiveIntervalUnion::Array Matrix;
53
54 // Cached queries per register unit.
55 std::unique_ptr<LiveIntervalUnion::Query[]> Queries;
56
57 // Cached register mask interference info.
58 unsigned RegMaskTag = 0;
59 Register RegMaskVirtReg;
60 BitVector RegMaskUsable;
61
62 LiveRegMatrix()
63 : LIUAlloc(std::make_unique<LiveIntervalUnion::Allocator>()) {};
64 void releaseMemory();
65
66public:
67 LiveRegMatrix(LiveRegMatrix &&Other) = default;
68
69 void init(MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM);
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(const LiveInterval &VirtReg,
109 MCRegister PhysReg);
110
111 /// Check for interference in the segment [Start, End) that may prevent
112 /// assignment to PhysReg. If this function returns true, there is
113 /// interference in the segment [Start, End) of some other interval already
114 /// assigned to PhysReg. If this function returns false, PhysReg is free at
115 /// the segment [Start, End).
116 bool checkInterference(SlotIndex Start, SlotIndex End, MCRegister PhysReg);
117
118 /// Check for interference in the segment [Start, End) that may prevent
119 /// assignment to PhysReg, like checkInterference. Returns a lane mask of
120 /// which lanes of the physical register interfere in the segment [Start, End)
121 /// of some other interval already assigned to PhysReg.
122 ///
123 /// If this function returns LaneBitmask::getNone(), PhysReg is completely
124 /// free at the segment [Start, End).
125 LaneBitmask checkInterferenceLanes(SlotIndex Start, SlotIndex End,
126 MCRegister PhysReg);
127
128 /// Assign VirtReg to PhysReg.
129 /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and
130 /// update VirtRegMap. The live range is expected to be available in PhysReg.
131 void assign(const LiveInterval &VirtReg, MCRegister PhysReg);
132
133 /// Unassign VirtReg from its PhysReg.
134 /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes
135 /// the assignment and updates VirtRegMap accordingly.
136 void unassign(const LiveInterval &VirtReg);
137
138 /// Returns true if the given \p PhysReg has any live intervals assigned.
139 bool isPhysRegUsed(MCRegister PhysReg) const;
140
141 //===--------------------------------------------------------------------===//
142 // Low-level interface.
143 //===--------------------------------------------------------------------===//
144 //
145 // Provide access to the underlying LiveIntervalUnions.
146 //
147
148 /// Check for regmask interference only.
149 /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg.
150 /// If PhysReg is null, check if VirtReg crosses any regmask operands.
151 bool checkRegMaskInterference(const LiveInterval &VirtReg,
152 MCRegister PhysReg = MCRegister::NoRegister);
153
154 /// Check for regunit interference only.
155 /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's
156 /// register units.
157 bool checkRegUnitInterference(const LiveInterval &VirtReg,
158 MCRegister PhysReg);
159
160 /// Query a line of the assigned virtual register matrix directly.
161 /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg.
162 /// This returns a reference to an internal Query data structure that is only
163 /// valid until the next query() call.
164 LiveIntervalUnion::Query &query(const LiveRange &LR, MCRegUnit RegUnit);
165
166 /// Directly access the live interval unions per regunit.
167 /// This returns an array indexed by the regunit number.
168 LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; }
169
170 Register getOneVReg(unsigned PhysReg) const;
171};
172
173class LiveRegMatrixWrapperLegacy : public MachineFunctionPass {
174 LiveRegMatrix LRM;
175
176public:
177 static char ID;
178
179 LiveRegMatrixWrapperLegacy() : MachineFunctionPass(ID) {}
180
181 LiveRegMatrix &getLRM() { return LRM; }
182 const LiveRegMatrix &getLRM() const { return LRM; }
183
184 void getAnalysisUsage(AnalysisUsage &AU) const override;
185 bool runOnMachineFunction(MachineFunction &MF) override;
186 void releaseMemory() override;
187};
188
189class LiveRegMatrixAnalysis : public AnalysisInfoMixin<LiveRegMatrixAnalysis> {
190 friend AnalysisInfoMixin<LiveRegMatrixAnalysis>;
191 static AnalysisKey Key;
192
193public:
194 using Result = LiveRegMatrix;
195
196 LiveRegMatrix run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM);
197};
198
199} // end namespace llvm
200
201#endif // LLVM_CODEGEN_LIVEREGMATRIX_H
202

source code of llvm/include/llvm/CodeGen/LiveRegMatrix.h