Line data Source code
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 :
32 : namespace llvm {
33 :
34 : class AnalysisUsage;
35 : class LiveInterval;
36 : class LiveIntervals;
37 : class MachineFunction;
38 : class TargetRegisterInfo;
39 : class VirtRegMap;
40 :
41 : class 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 :
66 : public:
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 1750306 : 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 17416069 : LiveIntervalUnion *getLiveUnions() { return &Matrix[0]; }
156 : };
157 :
158 : } // end namespace llvm
159 :
160 : #endif // LLVM_CODEGEN_LIVEREGMATRIX_H
|
