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
31namespace llvm {
32
33class LiveInterval;
34class LiveIntervalAnalysis;
35class MachineRegisterInfo;
36class TargetRegisterInfo;
37class VirtRegMap;
38
39class LiveRegMatrix : public MachineFunctionPass {
40  const TargetRegisterInfo *TRI;
41  MachineRegisterInfo *MRI;
42  LiveIntervals *LIS;
43  VirtRegMap *VRM;
44
45  // UserTag changes whenever virtual registers have been modified.
46  unsigned UserTag;
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;
57  unsigned RegMaskVirtReg;
58  BitVector RegMaskUsable;
59
60  // MachineFunctionPass boilerplate.
61  void getAnalysisUsage(AnalysisUsage&) const override;
62  bool runOnMachineFunction(MachineFunction&) override;
63  void releaseMemory() override;
64public:
65  static char ID;
66  LiveRegMatrix();
67
68  //===--------------------------------------------------------------------===//
69  // High-level interface.
70  //===--------------------------------------------------------------------===//
71  //
72  // Check for interference before assigning virtual registers to physical
73  // registers.
74  //
75
76  /// Invalidate cached interference queries after modifying virtual register
77  /// live ranges. Interference checks may return stale information unless
78  /// caches are invalidated.
79  void invalidateVirtRegs() { ++UserTag; }
80
81  enum InterferenceKind {
82    /// No interference, go ahead and assign.
83    IK_Free = 0,
84
85    /// Virtual register interference. There are interfering virtual registers
86    /// assigned to PhysReg or its aliases. This interference could be resolved
87    /// by unassigning those other virtual registers.
88    IK_VirtReg,
89
90    /// Register unit interference. A fixed live range is in the way, typically
91    /// argument registers for a call. This can't be resolved by unassigning
92    /// other virtual registers.
93    IK_RegUnit,
94
95    /// RegMask interference. The live range is crossing an instruction with a
96    /// regmask operand that doesn't preserve PhysReg. This typically means
97    /// VirtReg is live across a call, and PhysReg isn't call-preserved.
98    IK_RegMask
99  };
100
101  /// Check for interference before assigning VirtReg to PhysReg.
102  /// If this function returns IK_Free, it is legal to assign(VirtReg, PhysReg).
103  /// When there is more than one kind of interference, the InterferenceKind
104  /// with the highest enum value is returned.
105  InterferenceKind checkInterference(LiveInterval &VirtReg, unsigned PhysReg);
106
107  /// Assign VirtReg to PhysReg.
108  /// This will mark VirtReg's live range as occupied in the LiveRegMatrix and
109  /// update VirtRegMap. The live range is expected to be available in PhysReg.
110  void assign(LiveInterval &VirtReg, unsigned PhysReg);
111
112  /// Unassign VirtReg from its PhysReg.
113  /// Assuming that VirtReg was previously assigned to a PhysReg, this undoes
114  /// the assignment and updates VirtRegMap accordingly.
115  void unassign(LiveInterval &VirtReg);
116
117  //===--------------------------------------------------------------------===//
118  // Low-level interface.
119  //===--------------------------------------------------------------------===//
120  //
121  // Provide access to the underlying LiveIntervalUnions.
122  //
123
124  /// Check for regmask interference only.
125  /// Return true if VirtReg crosses a regmask operand that clobbers PhysReg.
126  /// If PhysReg is null, check if VirtReg crosses any regmask operands.
127  bool checkRegMaskInterference(LiveInterval &VirtReg, unsigned PhysReg = 0);
128
129  /// Check for regunit interference only.
130  /// Return true if VirtReg overlaps a fixed assignment of one of PhysRegs's
131  /// register units.
132  bool checkRegUnitInterference(LiveInterval &VirtReg, unsigned PhysReg);
133
134  /// Query a line of the assigned virtual register matrix directly.
135  /// Use MCRegUnitIterator to enumerate all regunits in the desired PhysReg.
136  /// This returns a reference to an internal Query data structure that is only
137  /// valid until the next query() call.
138  LiveIntervalUnion::Query &query(LiveInterval &VirtReg, unsigned RegUnit);
139
140  /// Directly access the live interval unions per regunit.
141  /// This returns an array indexed by the regunit number.
142  LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; }
143};
144
145} // end namespace llvm
146
147#endif // LLVM_CODEGEN_LIVEREGMATRIX_H
148