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;
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.
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(LiveInterval &VirtReg, unsigned PhysReg);
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, unsigned 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, unsigned 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(unsigned 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.
139  bool checkRegMaskInterference(LiveInterval &VirtReg, unsigned PhysReg = 0);
140
141  /// Check for regunit interference only.
142  /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's
143  /// register units.
144  bool checkRegUnitInterference(LiveInterval &VirtReg, unsigned PhysReg);
145
146  /// Query a line of the assigned virtual register matrix directly.
147  /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg.
148  /// This returns a reference to an internal Query data structure that is only
149  /// valid until the next query() call.
150  LiveIntervalUnion::Query &query(const LiveRange &LR, unsigned RegUnit);
151
152  /// Directly access the live interval unions per regunit.
153  /// This returns an array indexed by the regunit number.
154  LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; }
155};
156
157} // end namespace llvm
158
159#endif // LLVM_CODEGEN_LIVEREGMATRIX_H
160