xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/LiveRegMatrix.cpp (revision 0d8fe2373503aeac48492f28073049a8bfa4feb5)
1 //===- LiveRegMatrix.cpp - Track register interference --------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the LiveRegMatrix analysis pass.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/CodeGen/LiveRegMatrix.h"
14 #include "RegisterCoalescer.h"
15 #include "llvm/ADT/Statistic.h"
16 #include "llvm/CodeGen/LiveInterval.h"
17 #include "llvm/CodeGen/LiveIntervalUnion.h"
18 #include "llvm/CodeGen/LiveIntervals.h"
19 #include "llvm/CodeGen/MachineFunction.h"
20 #include "llvm/CodeGen/TargetRegisterInfo.h"
21 #include "llvm/CodeGen/TargetSubtargetInfo.h"
22 #include "llvm/CodeGen/VirtRegMap.h"
23 #include "llvm/InitializePasses.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 INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
40                       "Live Register Matrix", false, false)
41 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
42 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
43 INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix",
44                     "Live Register Matrix", false, false)
45 
46 LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {}
47 
48 void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
49   AU.setPreservesAll();
50   AU.addRequiredTransitive<LiveIntervals>();
51   AU.addRequiredTransitive<VirtRegMap>();
52   MachineFunctionPass::getAnalysisUsage(AU);
53 }
54 
55 bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) {
56   TRI = MF.getSubtarget().getRegisterInfo();
57   LIS = &getAnalysis<LiveIntervals>();
58   VRM = &getAnalysis<VirtRegMap>();
59 
60   unsigned NumRegUnits = TRI->getNumRegUnits();
61   if (NumRegUnits != Matrix.size())
62     Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
63   Matrix.init(LIUAlloc, NumRegUnits);
64 
65   // Make sure no stale queries get reused.
66   invalidateVirtRegs();
67   return false;
68 }
69 
70 void LiveRegMatrix::releaseMemory() {
71   for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {
72     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 }
78 
79 template <typename Callable>
80 static bool foreachUnit(const TargetRegisterInfo *TRI,
81                         LiveInterval &VRegInterval, MCRegister PhysReg,
82                         Callable Func) {
83   if (VRegInterval.hasSubRanges()) {
84     for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
85       unsigned Unit = (*Units).first;
86       LaneBitmask Mask = (*Units).second;
87       for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
88         if ((S.LaneMask & Mask).any()) {
89           if (Func(Unit, S))
90             return true;
91           break;
92         }
93       }
94     }
95   } else {
96     for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
97       if (Func(*Units, VRegInterval))
98         return true;
99     }
100   }
101   return false;
102 }
103 
104 void LiveRegMatrix::assign(LiveInterval &VirtReg, MCRegister PhysReg) {
105   LLVM_DEBUG(dbgs() << "assigning " << printReg(VirtReg.reg(), TRI) << " to "
106                     << printReg(PhysReg, TRI) << ':');
107   assert(!VRM->hasPhys(VirtReg.reg()) && "Duplicate VirtReg assignment");
108   VRM->assignVirt2Phys(VirtReg.reg(), PhysReg);
109 
110   foreachUnit(
111       TRI, VirtReg, PhysReg, [&](unsigned Unit, const LiveRange &Range) {
112         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 }
120 
121 void LiveRegMatrix::unassign(LiveInterval &VirtReg) {
122   Register PhysReg = VRM->getPhys(VirtReg.reg());
123   LLVM_DEBUG(dbgs() << "unassigning " << printReg(VirtReg.reg(), TRI)
124                     << " from " << printReg(PhysReg, TRI) << ':');
125   VRM->clearVirt(VirtReg.reg());
126 
127   foreachUnit(TRI, VirtReg, PhysReg,
128               [&](unsigned Unit, const LiveRange &Range) {
129                 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI));
130                 Matrix[Unit].extract(VirtReg, Range);
131                 return false;
132               });
133 
134   ++NumUnassigned;
135   LLVM_DEBUG(dbgs() << '\n');
136 }
137 
138 bool LiveRegMatrix::isPhysRegUsed(MCRegister PhysReg) const {
139   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
140     if (!Matrix[*Unit].empty())
141       return true;
142   }
143   return false;
144 }
145 
146 bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg,
147                                              MCRegister PhysReg) {
148   // Check if the cached information is valid.
149   // 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     RegMaskVirtReg = VirtReg.reg();
153     RegMaskTag = UserTag;
154     RegMaskUsable.clear();
155     LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
156   }
157 
158   // 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                                              MCRegister PhysReg) {
166   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     const LiveRange &UnitRange = LIS->getRegUnit(Unit);
173     return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());
174   });
175   return Result;
176 }
177 
178 LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR,
179                                                MCRegister RegUnit) {
180   LiveIntervalUnion::Query &Q = Queries[RegUnit];
181   Q.init(UserTag, LR, Matrix[RegUnit]);
182   return Q;
183 }
184 
185 LiveRegMatrix::InterferenceKind
186 LiveRegMatrix::checkInterference(LiveInterval &VirtReg, MCRegister PhysReg) {
187   if (VirtReg.empty())
188     return IK_Free;
189 
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     return IK_RegUnit;
197 
198   // Check the matrix for virtual register interference.
199   bool Interference = foreachUnit(TRI, VirtReg, PhysReg,
200                                   [&](MCRegister Unit, const LiveRange &LR) {
201                                     return query(LR, Unit).checkInterference();
202                                   });
203   if (Interference)
204     return IK_VirtReg;
205 
206   return IK_Free;
207 }
208 
209 bool LiveRegMatrix::checkInterference(SlotIndex Start, SlotIndex End,
210                                       MCRegister PhysReg) {
211   // Construct artificial live range containing only one segment [Start, End).
212   VNInfo valno(0, Start);
213   LiveRange::Segment Seg(Start, End, &valno);
214   LiveRange LR;
215   LR.addSegment(Seg);
216 
217   // Check for interference with that segment
218   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
219     if (query(LR, *Units).checkInterference())
220       return true;
221   }
222   return false;
223 }
224 
225 Register LiveRegMatrix::getOneVReg(unsigned PhysReg) const {
226   LiveInterval *VRegInterval = nullptr;
227   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
228     if ((VRegInterval = Matrix[*Unit].getOneVReg()))
229       return VRegInterval->reg();
230   }
231 
232   return MCRegister::NoRegister;
233 }
234