1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
| //===- LiveRegMatrix.h - Track register interference ----------*- C++ -*---===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// The LiveRegMatrix analysis pass keeps track of virtual register interference
// along two dimensions: Slot indexes and register units. The matrix is used by
// register allocators to ensure that no interfering virtual registers get
// assigned to overlapping physical registers.
//
// Register units are defined in MCRegisterInfo.h, they represent the smallest
// unit of interference when dealing with overlapping physical registers. The
// LiveRegMatrix is represented as a LiveIntervalUnion per register unit. When
// a virtual register is assigned to a physical register, the live range for
// the virtual register is inserted into the LiveIntervalUnion for each regunit
// in the physreg.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_LIVEREGMATRIX_H
#define LLVM_CODEGEN_LIVEREGMATRIX_H
#include "llvm/ADT/BitVector.h"
#include "llvm/CodeGen/LiveIntervalUnion.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include <memory>
namespace llvm {
class AnalysisUsage;
class LiveInterval;
class LiveIntervals;
class MachineFunction;
class TargetRegisterInfo;
class VirtRegMap;
class LiveRegMatrix : public MachineFunctionPass {
const TargetRegisterInfo *TRI;
LiveIntervals *LIS;
VirtRegMap *VRM;
// UserTag changes whenever virtual registers have been modified.
unsigned UserTag = 0;
// The matrix is represented as a LiveIntervalUnion per register unit.
LiveIntervalUnion::Allocator LIUAlloc;
LiveIntervalUnion::Array Matrix;
// Cached queries per register unit.
std::unique_ptr<LiveIntervalUnion::Query[]> Queries;
// Cached register mask interference info.
unsigned RegMaskTag = 0;
unsigned RegMaskVirtReg = 0;
BitVector RegMaskUsable;
// MachineFunctionPass boilerplate.
void getAnalysisUsage(AnalysisUsage &) const override;
bool runOnMachineFunction(MachineFunction &) override;
void releaseMemory() override;
public:
static char ID;
LiveRegMatrix();
//===--------------------------------------------------------------------===//
// High-level interface.
//===--------------------------------------------------------------------===//
//
// Check for interference before assigning virtual registers to physical
// registers.
//
/// Invalidate cached interference queries after modifying virtual register
/// live ranges. Interference checks may return stale information unless
/// caches are invalidated.
void invalidateVirtRegs() { ++UserTag; }
enum InterferenceKind {
/// No interference, go ahead and assign.
IK_Free = 0,
/// Virtual register interference. There are interfering virtual registers
/// assigned to PhysReg or its aliases. This interference could be resolved
/// by unassigning those other virtual registers.
IK_VirtReg,
/// Register unit interference. A fixed live range is in the way, typically
/// argument registers for a call. This can't be resolved by unassigning
/// other virtual registers.
IK_RegUnit,
/// RegMask interference. The live range is crossing an instruction with a
/// regmask operand that doesn't preserve PhysReg. This typically means
/// VirtReg is live across a call, and PhysReg isn't call-preserved.
IK_RegMask
};
/// Check for interference before assigning VirtReg to PhysReg.
/// If this function returns IK_Free, it is legal to assign(VirtReg, PhysReg).
/// When there is more than one kind of interference, the InterferenceKind
/// with the highest enum value is returned.
InterferenceKind checkInterference(LiveInterval &VirtReg, unsigned PhysReg);
/// Check for interference in the segment [Start, End) that may prevent
/// assignment to PhysReg. If this function returns true, there is
/// interference in the segment [Start, End) of some other interval already
/// assigned to PhysReg. If this function returns false, PhysReg is free at
/// the segment [Start, End).
bool checkInterference(SlotIndex Start, SlotIndex End, unsigned PhysReg);
/// Assign VirtReg to PhysReg.
/// This will mark VirtReg's live range as occupied in the LiveRegMatrix and
/// update VirtRegMap. The live range is expected to be available in PhysReg.
void assign(LiveInterval &VirtReg, unsigned PhysReg);
/// Unassign VirtReg from its PhysReg.
/// Assuming that VirtReg was previously assigned to a PhysReg, this undoes
/// the assignment and updates VirtRegMap accordingly.
void unassign(LiveInterval &VirtReg);
/// Returns true if the given \p PhysReg has any live intervals assigned.
bool isPhysRegUsed(unsigned PhysReg) const;
//===--------------------------------------------------------------------===//
// Low-level interface.
//===--------------------------------------------------------------------===//
//
// Provide access to the underlying LiveIntervalUnions.
//
/// Check for regmask interference only.
/// Return true if VirtReg crosses a regmask operand that clobbers PhysReg.
/// If PhysReg is null, check if VirtReg crosses any regmask operands.
bool checkRegMaskInterference(LiveInterval &VirtReg, unsigned PhysReg = 0);
/// Check for regunit interference only.
/// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's
/// register units.
bool checkRegUnitInterference(LiveInterval &VirtReg, unsigned PhysReg);
/// Query a line of the assigned virtual register matrix directly.
/// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg.
/// This returns a reference to an internal Query data structure that is only
/// valid until the next query() call.
LiveIntervalUnion::Query &query(const LiveRange &LR, unsigned RegUnit);
/// Directly access the live interval unions per regunit.
/// This returns an array indexed by the regunit number.
LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; }
};
} // end namespace llvm
#endif // LLVM_CODEGEN_LIVEREGMATRIX_H
|