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