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