Line data Source code
1 : //===- LiveRegMatrix.cpp - Track register interference --------------------===//
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 : // This file defines the LiveRegMatrix analysis pass.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #include "llvm/CodeGen/LiveRegMatrix.h"
15 : #include "RegisterCoalescer.h"
16 : #include "llvm/ADT/Statistic.h"
17 : #include "llvm/CodeGen/LiveInterval.h"
18 : #include "llvm/CodeGen/LiveIntervalUnion.h"
19 : #include "llvm/CodeGen/LiveIntervals.h"
20 : #include "llvm/CodeGen/MachineFunction.h"
21 : #include "llvm/CodeGen/TargetRegisterInfo.h"
22 : #include "llvm/CodeGen/TargetSubtargetInfo.h"
23 : #include "llvm/CodeGen/VirtRegMap.h"
24 : #include "llvm/MC/LaneBitmask.h"
25 : #include "llvm/MC/MCRegisterInfo.h"
26 : #include "llvm/Pass.h"
27 : #include "llvm/Support/Debug.h"
28 : #include "llvm/Support/raw_ostream.h"
29 : #include <cassert>
30 :
31 : using namespace llvm;
32 :
33 : #define DEBUG_TYPE "regalloc"
34 :
35 : STATISTIC(NumAssigned , "Number of registers assigned");
36 : STATISTIC(NumUnassigned , "Number of registers unassigned");
37 :
38 : char LiveRegMatrix::ID = 0;
39 31780 : INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
40 : "Live Register Matrix", false, false)
41 31780 : INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
42 31780 : INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
43 95340 : INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix",
44 : "Live Register Matrix", false, false)
45 :
46 19532 : LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {}
47 :
48 19532 : void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
49 : AU.setPreservesAll();
50 : AU.addRequiredTransitive<LiveIntervals>();
51 : AU.addRequiredTransitive<VirtRegMap>();
52 19532 : MachineFunctionPass::getAnalysisUsage(AU);
53 19532 : }
54 :
55 193992 : bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) {
56 193992 : TRI = MF.getSubtarget().getRegisterInfo();
57 193992 : LIS = &getAnalysis<LiveIntervals>();
58 193992 : VRM = &getAnalysis<VirtRegMap>();
59 :
60 193992 : unsigned NumRegUnits = TRI->getNumRegUnits();
61 193992 : if (NumRegUnits != Matrix.size())
62 3762307 : Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
63 193992 : Matrix.init(LIUAlloc, NumRegUnits);
64 :
65 : // Make sure no stale queries get reused.
66 : invalidateVirtRegs();
67 193992 : return false;
68 : }
69 :
70 194006 : void LiveRegMatrix::releaseMemory() {
71 38851723 : for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {
72 38657717 : Matrix[i].clear();
73 : // No need to clear Queries here, since LiveIntervalUnion::Query doesn't
74 : // have anything important to clear and LiveRegMatrix's runOnFunction()
75 : // does a std::unique_ptr::reset anyways.
76 : }
77 194006 : }
78 :
79 : template <typename Callable>
80 12125609 : static bool foreachUnit(const TargetRegisterInfo *TRI,
81 : LiveInterval &VRegInterval, unsigned PhysReg,
82 : Callable Func) {
83 12125609 : if (VRegInterval.hasSubRanges()) {
84 6219490 : for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
85 : unsigned Unit = (*Units).first;
86 : LaneBitmask Mask = (*Units).second;
87 7946414 : for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
88 15844010 : if ((S.LaneMask & Mask).any()) {
89 3823910 : if (Func(Unit, S))
90 : return true;
91 : break;
92 : }
93 : }
94 : }
95 : } else {
96 33147371 : for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
97 28491850 : if (Func(*Units, VRegInterval))
98 : return true;
99 : }
100 : }
101 : return false;
102 : }
103 4916807 :
104 : void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) {
105 : LLVM_DEBUG(dbgs() << "assigning " << printReg(VirtReg.reg, TRI) << " to "
106 4916807 : << printReg(PhysReg, TRI) << ':');
107 1405514 : assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
108 : VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
109 :
110 1193376 : foreachUnit(
111 2378210 : TRI, VirtReg, PhysReg, [&](unsigned Unit, const LiveRange &Range) {
112 753503 : LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << ' ' << Range);
113 : Matrix[Unit].unify(VirtReg, Range);
114 : return false;
115 : });
116 :
117 : ++NumAssigned;
118 : LLVM_DEBUG(dbgs() << '\n');
119 10917991 : }
120 10450808 :
121 : void LiveRegMatrix::unassign(LiveInterval &VirtReg) {
122 : unsigned PhysReg = VRM->getPhys(VirtReg.reg);
123 : LLVM_DEBUG(dbgs() << "unassigning " << printReg(VirtReg.reg, TRI) << " from "
124 : << printReg(PhysReg, TRI) << ':');
125 : VRM->clearVirt(VirtReg.reg);
126 5674436 :
127 : foreachUnit(TRI, VirtReg, PhysReg,
128 : [&](unsigned Unit, const LiveRange &Range) {
129 5674436 : LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI));
130 4470198 : Matrix[Unit].extract(VirtReg, Range);
131 : return false;
132 : });
133 6244511 :
134 12456986 : ++NumUnassigned;
135 2863151 : LLVM_DEBUG(dbgs() << '\n');
136 : }
137 :
138 : bool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const {
139 : for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
140 : if (!Matrix[*Unit].empty())
141 : return true;
142 16748420 : }
143 15496412 : return false;
144 : }
145 :
146 : bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg,
147 : unsigned PhysReg) {
148 : // Check if the cached information is valid.
149 63177 : // The same BitVector can be reused for all PhysRegs.
150 : // We could cache multiple VirtRegs if it becomes necessary.
151 : if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) {
152 63177 : RegMaskVirtReg = VirtReg.reg;
153 4404 : RegMaskTag = UserTag;
154 : RegMaskUsable.clear();
155 : LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
156 6377 : }
157 12746 :
158 2758 : // The BitVector is indexed by PhysReg, not register unit.
159 : // Regmask interference is more fine grained than regunits.
160 : // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
161 : return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
162 : }
163 :
164 : bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg,
165 297308 : unsigned PhysReg) {
166 172596 : if (VirtReg.empty())
167 : return false;
168 : CoalescerPair CP(VirtReg.reg, PhysReg, *TRI);
169 :
170 : bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
171 : const LiveRange &Range) {
172 1471189 : const LiveRange &UnitRange = LIS->getRegUnit(Unit);
173 : return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());
174 : });
175 1471189 : return Result;
176 339374 : }
177 :
178 : LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR,
179 502150 : unsigned RegUnit) {
180 996068 : LiveIntervalUnion::Query &Q = Queries[RegUnit];
181 204498 : Q.init(UserTag, LR, Matrix[RegUnit]);
182 : return Q;
183 : }
184 :
185 : LiveRegMatrix::InterferenceKind
186 : LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
187 : if (VirtReg.empty())
188 5183652 : return IK_Free;
189 2372034 :
190 : // Regmask interference is the fastest check.
191 : if (checkRegMaskInterference(VirtReg, PhysReg))
192 : return IK_RegMask;
193 :
194 : // Check for fixed interference.
195 : if (checkRegUnitInterference(VirtReg, PhysReg))
196 1471189 : return IK_RegUnit;
197 :
198 : // Check the matrix for virtual register interference.
199 : bool Interference = foreachUnit(TRI, VirtReg, PhysReg,
200 1471189 : [&](unsigned Unit, const LiveRange &LR) {
201 : return query(LR, Unit).checkInterference();
202 1471189 : });
203 : if (Interference)
204 : return IK_VirtReg;
205 5153064 :
206 : return IK_Free;
207 : }
208 :
209 : bool LiveRegMatrix::checkInterference(SlotIndex Start, SlotIndex End,
210 : unsigned PhysReg) {
211 1471189 : // Construct artificial live range containing only one segment [Start, End).
212 : VNInfo valno(0, Start);
213 63177 : LiveRange::Segment Seg(Start, End, &valno);
214 63177 : LiveRange LR;
215 : LR.addSegment(Seg);
216 :
217 : // Check for interference with that segment
218 : for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
219 63177 : if (query(LR, *Units).checkInterference())
220 : return true;
221 : }
222 350708 : return false;
223 : }
|
