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 : public MachineFunctionPass {
41 const TargetRegisterInfo *TRI = nullptr;
42 LiveIntervals *LIS = nullptr;
43 VirtRegMap *VRM = nullptr;
44
45 // UserTag changes whenever virtual registers have been modified.
46 unsigned UserTag = 0;
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 = 0;
57 unsigned RegMaskVirtReg = 0;
58 BitVector RegMaskUsable;
59
60 // MachineFunctionPass boilerplate.
61 void getAnalysisUsage(AnalysisUsage &) const override;
62 bool runOnMachineFunction(MachineFunction &) override;
63 void releaseMemory() override;
64
65public:
66 static char ID;
67
68 LiveRegMatrix();
69
70 //===--------------------------------------------------------------------===//
71 // High-level interface.
72 //===--------------------------------------------------------------------===//
73 //
74 // Check for interference before assigning virtual registers to physical
75 // registers.
76 //
77
78 /// Invalidate cached interference queries after modifying virtual register
79 /// live ranges. Interference checks may return stale information unless
80 /// caches are invalidated.
81 void invalidateVirtRegs() { ++UserTag; }
82
83 enum InterferenceKind {
84 /// No interference, go ahead and assign.
85 IK_Free = 0,
86
87 /// Virtual register interference. There are interfering virtual registers
88 /// assigned to PhysReg or its aliases. This interference could be resolved
89 /// by unassigning those other virtual registers.
90 IK_VirtReg,
91
92 /// Register unit interference. A fixed live range is in the way, typically
93 /// argument registers for a call. This can't be resolved by unassigning
94 /// other virtual registers.
95 IK_RegUnit,
96
97 /// RegMask interference. The live range is crossing an instruction with a
98 /// regmask operand that doesn't preserve PhysReg. This typically means
99 /// VirtReg is live across a call, and PhysReg isn't call-preserved.
100 IK_RegMask
101 };
102
103 /// Check for interference before assigning VirtReg to PhysReg.
104 /// If this function returns IK_Free, it is legal to assign(VirtReg, PhysReg).
105 /// When there is more than one kind of interference, the InterferenceKind
106 /// with the highest enum value is returned.
107 InterferenceKind checkInterference(const LiveInterval &VirtReg,
108 MCRegister PhysReg);
109
110 /// Check for interference in the segment [Start, End) that may prevent
111 /// assignment to PhysReg. If this function returns true, there is
112 /// interference in the segment [Start, End) of some other interval already
113 /// assigned to PhysReg. If this function returns false, PhysReg is free at
114 /// the segment [Start, End).
115 bool checkInterference(SlotIndex Start, SlotIndex End, MCRegister PhysReg);
116
117 /// Assign VirtReg to PhysReg.
118 /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and
119 /// update VirtRegMap. The live range is expected to be available in PhysReg.
120 void assign(const LiveInterval &VirtReg, MCRegister PhysReg);
121
122 /// Unassign VirtReg from its PhysReg.
123 /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes
124 /// the assignment and updates VirtRegMap accordingly.
125 void unassign(const LiveInterval &VirtReg);
126
127 /// Returns true if the given \p PhysReg has any live intervals assigned.
128 bool isPhysRegUsed(MCRegister PhysReg) const;
129
130 //===--------------------------------------------------------------------===//
131 // Low-level interface.
132 //===--------------------------------------------------------------------===//
133 //
134 // Provide access to the underlying LiveIntervalUnions.
135 //
136
137 /// Check for regmask interference only.
138 /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg.
139 /// If PhysReg is null, check if VirtReg crosses any regmask operands.
140 bool checkRegMaskInterference(const LiveInterval &VirtReg,
141 MCRegister PhysReg = MCRegister::NoRegister);
142
143 /// Check for regunit interference only.
144 /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's
145 /// register units.
146 bool checkRegUnitInterference(const LiveInterval &VirtReg,
147 MCRegister PhysReg);
148
149 /// Query a line of the assigned virtual register matrix directly.
150 /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg.
151 /// This returns a reference to an internal Query data structure that is only
152 /// valid until the next query() call.
153 LiveIntervalUnion::Query &query(const LiveRange &LR, MCRegister RegUnit);
154
155 /// Directly access the live interval unions per regunit.
156 /// This returns an array indexed by the regunit number.
157 LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; }
158
159 Register getOneVReg(unsigned PhysReg) const;
160};
161
162} // end namespace llvm
163
164#endif // LLVM_CODEGEN_LIVEREGMATRIX_H
165

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