blob: f62a55c7308558fc9d45f61314941617cb2589a8 [file] [log] [blame]
Andrew Scull5e1ddfa2018-08-14 10:06:54 +01001//===- 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 /// 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, unsigned 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(LiveInterval &VirtReg, unsigned 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(LiveInterval &VirtReg);
126
127 /// Returns true if the given \p PhysReg has any live intervals assigned.
128 bool isPhysRegUsed(unsigned 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(LiveInterval &VirtReg, unsigned PhysReg = 0);
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, unsigned 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, unsigned RegUnit);
152
153 /// Directly access the live interval unions per regunit.
154 /// This returns an array indexed by the regunit number.
155 LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; }
156};
157
158} // end namespace llvm
159
160#endif // LLVM_CODEGEN_LIVEREGMATRIX_H