LLVM  13.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 
31 namespace llvm {
32 
33 class AnalysisUsage;
34 class LiveInterval;
35 class LiveIntervals;
36 class MachineFunction;
37 class TargetRegisterInfo;
38 class 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 
65 public:
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 
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.
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 
109  /// Check for interference in the segment [Start, End) that may prevent
110  /// assignment to PhysReg. If this function returns true, there is
111  /// interference in the segment [Start, End) of some other interval already
112  /// assigned to PhysReg. If this function returns false, PhysReg is free at
113  /// the segment [Start, End).
114  bool checkInterference(SlotIndex Start, SlotIndex End, MCRegister PhysReg);
115 
116  /// Assign VirtReg to PhysReg.
117  /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and
118  /// update VirtRegMap. The live range is expected to be available in PhysReg.
119  void assign(LiveInterval &VirtReg, MCRegister PhysReg);
120 
121  /// Unassign VirtReg from its PhysReg.
122  /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes
123  /// the assignment and updates VirtRegMap accordingly.
124  void unassign(LiveInterval &VirtReg);
125 
126  /// Returns true if the given \p PhysReg has any live intervals assigned.
127  bool isPhysRegUsed(MCRegister PhysReg) const;
128 
129  //===--------------------------------------------------------------------===//
130  // Low-level interface.
131  //===--------------------------------------------------------------------===//
132  //
133  // Provide access to the underlying LiveIntervalUnions.
134  //
135 
136  /// Check for regmask interference only.
137  /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg.
138  /// If PhysReg is null, check if VirtReg crosses any regmask operands.
141 
142  /// Check for regunit interference only.
143  /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's
144  /// register units.
145  bool checkRegUnitInterference(LiveInterval &VirtReg, MCRegister PhysReg);
146 
147  /// Query a line of the assigned virtual register matrix directly.
148  /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg.
149  /// This returns a reference to an internal Query data structure that is only
150  /// valid until the next query() call.
151  LiveIntervalUnion::Query &query(const LiveRange &LR, MCRegister RegUnit);
152 
153  /// Directly access the live interval unions per regunit.
154  /// This returns an array indexed by the regunit number.
156 
157  Register getOneVReg(unsigned PhysReg) const;
158 };
159 
160 } // end namespace llvm
161 
162 #endif // LLVM_CODEGEN_LIVEREGMATRIX_H
llvm::LiveRegMatrix::InterferenceKind
InterferenceKind
Definition: LiveRegMatrix.h:83
llvm::LiveIntervalUnion::Array
Definition: LiveIntervalUnion.h:172
llvm
Definition: AllocatorList.h:23
llvm::LiveRegMatrix::checkInterference
InterferenceKind checkInterference(LiveInterval &VirtReg, MCRegister PhysReg)
Check for interference before assigning VirtReg to PhysReg.
Definition: LiveRegMatrix.cpp:186
llvm::LiveRegMatrix::invalidateVirtRegs
void invalidateVirtRegs()
Invalidate cached interference queries after modifying virtual register live ranges.
Definition: LiveRegMatrix.h:81
llvm::LiveRegMatrix::getLiveUnions
LiveIntervalUnion * getLiveUnions()
Directly access the live interval unions per regunit.
Definition: LiveRegMatrix.h:155
llvm::VirtRegMap
Definition: VirtRegMap.h:33
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:231
llvm::MCRegister::NoRegister
static constexpr unsigned NoRegister
Definition: MCRegister.h:41
llvm::LiveIntervalUnion::Allocator
LiveSegments::Allocator Allocator
Definition: LiveIntervalUnion.h:58
llvm::LiveRegMatrix::getOneVReg
Register getOneVReg(unsigned PhysReg) const
Definition: LiveRegMatrix.cpp:239
llvm::LiveRegMatrix::IK_RegUnit
@ IK_RegUnit
Register unit interference.
Definition: LiveRegMatrix.h:95
llvm::LiveRegMatrix::IK_Free
@ IK_Free
No interference, go ahead and assign.
Definition: LiveRegMatrix.h:85
llvm::LiveRegMatrix::checkRegMaskInterference
bool checkRegMaskInterference(LiveInterval &VirtReg, MCRegister PhysReg=MCRegister::NoRegister)
Check for regmask interference only.
Definition: LiveRegMatrix.cpp:146
llvm::LiveRegMatrix::assign
void assign(LiveInterval &VirtReg, MCRegister PhysReg)
Assign VirtReg to PhysReg.
Definition: LiveRegMatrix.cpp:104
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
LiveIntervalUnion.h
llvm::LiveRegMatrix::isPhysRegUsed
bool isPhysRegUsed(MCRegister PhysReg) const
Returns true if the given PhysReg has any live intervals assigned.
Definition: LiveRegMatrix.cpp:138
BitVector.h
llvm::BitVector
Definition: BitVector.h:74
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:680
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
llvm::LiveRegMatrix::query
LiveIntervalUnion::Query & query(const LiveRange &LR, MCRegister RegUnit)
Query a line of the assigned virtual register matrix directly.
Definition: LiveRegMatrix.cpp:178
llvm::LiveRegMatrix::unassign
void unassign(LiveInterval &VirtReg)
Unassign VirtReg from its PhysReg.
Definition: LiveRegMatrix.cpp:121
llvm::LiveRange
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
MachineFunctionPass.h
llvm::LiveIntervalUnion
Union of live intervals that are strong candidates for coalescing into a single register (either phys...
Definition: LiveIntervalUnion.h:42
llvm::LiveRegMatrix::checkRegUnitInterference
bool checkRegUnitInterference(LiveInterval &VirtReg, MCRegister PhysReg)
Check for regunit interference only.
Definition: LiveRegMatrix.cpp:164
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::LiveRegMatrix::IK_VirtReg
@ IK_VirtReg
Virtual register interference.
Definition: LiveRegMatrix.h:90
Matrix
Live Register Matrix
Definition: LiveRegMatrix.cpp:44
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::LiveRegMatrix::IK_RegMask
@ IK_RegMask
RegMask interference.
Definition: LiveRegMatrix.h:100
llvm::LiveIntervals
Definition: LiveIntervals.h:54
llvm::LiveIntervalUnion::Query
Query interferences between a single live virtual register and a live interval union.
Definition: LiveIntervalUnion.h:112
llvm::LiveRegMatrix::ID
static char ID
Definition: LiveRegMatrix.h:66
llvm::LiveRegMatrix::LiveRegMatrix
LiveRegMatrix()
Definition: LiveRegMatrix.cpp:46
llvm::MCRegister
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:22
llvm::LiveRegMatrix
Definition: LiveRegMatrix.h:40