LLVM 17.0.0git
LiveRegMatrix.h
Go to the documentation of this file.
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"
29#include <memory>
30
31namespace llvm {
32
33class AnalysisUsage;
34class LiveInterval;
35class LiveIntervals;
36class MachineFunction;
37class TargetRegisterInfo;
38class VirtRegMap;
39
41 const TargetRegisterInfo *TRI;
42 LiveIntervals *LIS;
43 VirtRegMap *VRM;
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.
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
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
84 /// No interference, go ahead and assign.
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.
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.
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.
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.
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,
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.
154
155 /// Directly access the live interval unions per regunit.
156 /// This returns an array indexed by the regunit number.
158
159 Register getOneVReg(unsigned PhysReg) const;
160};
161
162} // end namespace llvm
163
164#endif // LLVM_CODEGEN_LIVEREGMATRIX_H
This file implements the BitVector class.
Live Register Matrix
Represent the analysis usage information of a pass.
Query interferences between a single live virtual register and a live interval union.
Union of live intervals that are strong candidates for coalescing into a single register (either phys...
LiveSegments::Allocator Allocator
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
bool checkRegMaskInterference(const LiveInterval &VirtReg, MCRegister PhysReg=MCRegister::NoRegister)
Check for regmask interference only.
void unassign(const LiveInterval &VirtReg)
Unassign VirtReg from its PhysReg.
LiveIntervalUnion::Query & query(const LiveRange &LR, MCRegister RegUnit)
Query a line of the assigned virtual register matrix directly.
bool isPhysRegUsed(MCRegister PhysReg) const
Returns true if the given PhysReg has any live intervals assigned.
void invalidateVirtRegs()
Invalidate cached interference queries after modifying virtual register live ranges.
Definition: LiveRegMatrix.h:81
Register getOneVReg(unsigned PhysReg) const
@ IK_VirtReg
Virtual register interference.
Definition: LiveRegMatrix.h:90
@ IK_RegUnit
Register unit interference.
Definition: LiveRegMatrix.h:95
@ IK_Free
No interference, go ahead and assign.
Definition: LiveRegMatrix.h:85
@ IK_RegMask
RegMask interference.
void assign(const LiveInterval &VirtReg, MCRegister PhysReg)
Assign VirtReg to PhysReg.
InterferenceKind checkInterference(const LiveInterval &VirtReg, MCRegister PhysReg)
Check for interference before assigning VirtReg to PhysReg.
bool checkRegUnitInterference(const LiveInterval &VirtReg, MCRegister PhysReg)
Check for regunit interference only.
LiveIntervalUnion * getLiveUnions()
Directly access the live interval unions per regunit.
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24
static constexpr unsigned NoRegister
Definition: MCRegister.h:43
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:82
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18