15db84df7SEugene Zelenko //===- LiveRegMatrix.cpp - Track register interference --------------------===//
2c26fbbfbSJakob Stoklund Olesen //
3*2946cd70SChandler Carruth // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4*2946cd70SChandler Carruth // See https://llvm.org/LICENSE.txt for license information.
5*2946cd70SChandler Carruth // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6c26fbbfbSJakob Stoklund Olesen //
7c26fbbfbSJakob Stoklund Olesen //===----------------------------------------------------------------------===//
8c26fbbfbSJakob Stoklund Olesen //
9c26fbbfbSJakob Stoklund Olesen // This file defines the LiveRegMatrix analysis pass.
10c26fbbfbSJakob Stoklund Olesen //
11c26fbbfbSJakob Stoklund Olesen //===----------------------------------------------------------------------===//
12c26fbbfbSJakob Stoklund Olesen 
136bda14b3SChandler Carruth #include "llvm/CodeGen/LiveRegMatrix.h"
14866908c4SJakob Stoklund Olesen #include "RegisterCoalescer.h"
15c26fbbfbSJakob Stoklund Olesen #include "llvm/ADT/Statistic.h"
165db84df7SEugene Zelenko #include "llvm/CodeGen/LiveInterval.h"
175db84df7SEugene Zelenko #include "llvm/CodeGen/LiveIntervalUnion.h"
18f842297dSMatthias Braun #include "llvm/CodeGen/LiveIntervals.h"
195db84df7SEugene Zelenko #include "llvm/CodeGen/MachineFunction.h"
20b3bde2eaSDavid Blaikie #include "llvm/CodeGen/TargetRegisterInfo.h"
21b3bde2eaSDavid Blaikie #include "llvm/CodeGen/TargetSubtargetInfo.h"
226bda14b3SChandler Carruth #include "llvm/CodeGen/VirtRegMap.h"
235db84df7SEugene Zelenko #include "llvm/MC/LaneBitmask.h"
245db84df7SEugene Zelenko #include "llvm/MC/MCRegisterInfo.h"
256bda14b3SChandler Carruth #include "llvm/Pass.h"
26c26fbbfbSJakob Stoklund Olesen #include "llvm/Support/Debug.h"
27d9903888SChandler Carruth #include "llvm/Support/raw_ostream.h"
285db84df7SEugene Zelenko #include <cassert>
29c26fbbfbSJakob Stoklund Olesen 
30c26fbbfbSJakob Stoklund Olesen using namespace llvm;
31c26fbbfbSJakob Stoklund Olesen 
321b9dde08SChandler Carruth #define DEBUG_TYPE "regalloc"
331b9dde08SChandler Carruth 
34c26fbbfbSJakob Stoklund Olesen STATISTIC(NumAssigned   , "Number of registers assigned");
35c26fbbfbSJakob Stoklund Olesen STATISTIC(NumUnassigned , "Number of registers unassigned");
36c26fbbfbSJakob Stoklund Olesen 
37c26fbbfbSJakob Stoklund Olesen char LiveRegMatrix::ID = 0;
38c26fbbfbSJakob Stoklund Olesen INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
39c26fbbfbSJakob Stoklund Olesen                       "Live Register Matrix", false, false)
40c26fbbfbSJakob Stoklund Olesen INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
41c26fbbfbSJakob Stoklund Olesen INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
42c26fbbfbSJakob Stoklund Olesen INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix",
43c26fbbfbSJakob Stoklund Olesen                     "Live Register Matrix", false, false)
44c26fbbfbSJakob Stoklund Olesen 
455db84df7SEugene Zelenko LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {}
46c26fbbfbSJakob Stoklund Olesen 
47c26fbbfbSJakob Stoklund Olesen void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
48c26fbbfbSJakob Stoklund Olesen   AU.setPreservesAll();
49c26fbbfbSJakob Stoklund Olesen   AU.addRequiredTransitive<LiveIntervals>();
50c26fbbfbSJakob Stoklund Olesen   AU.addRequiredTransitive<VirtRegMap>();
51c26fbbfbSJakob Stoklund Olesen   MachineFunctionPass::getAnalysisUsage(AU);
52c26fbbfbSJakob Stoklund Olesen }
53c26fbbfbSJakob Stoklund Olesen 
54c26fbbfbSJakob Stoklund Olesen bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) {
55fc6de428SEric Christopher   TRI = MF.getSubtarget().getRegisterInfo();
56c26fbbfbSJakob Stoklund Olesen   LIS = &getAnalysis<LiveIntervals>();
57c26fbbfbSJakob Stoklund Olesen   VRM = &getAnalysis<VirtRegMap>();
58c26fbbfbSJakob Stoklund Olesen 
59c26fbbfbSJakob Stoklund Olesen   unsigned NumRegUnits = TRI->getNumRegUnits();
60c26fbbfbSJakob Stoklund Olesen   if (NumRegUnits != Matrix.size())
61c26fbbfbSJakob Stoklund Olesen     Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
62c26fbbfbSJakob Stoklund Olesen   Matrix.init(LIUAlloc, NumRegUnits);
63c26fbbfbSJakob Stoklund Olesen 
64c26fbbfbSJakob Stoklund Olesen   // Make sure no stale queries get reused.
65c26fbbfbSJakob Stoklund Olesen   invalidateVirtRegs();
66c26fbbfbSJakob Stoklund Olesen   return false;
67c26fbbfbSJakob Stoklund Olesen }
68c26fbbfbSJakob Stoklund Olesen 
69c26fbbfbSJakob Stoklund Olesen void LiveRegMatrix::releaseMemory() {
70c26fbbfbSJakob Stoklund Olesen   for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {
71c26fbbfbSJakob Stoklund Olesen     Matrix[i].clear();
7212ae04bdSPuyan Lotfi     // No need to clear Queries here, since LiveIntervalUnion::Query doesn't
7312ae04bdSPuyan Lotfi     // have anything important to clear and LiveRegMatrix's runOnFunction()
7456440fd8SAhmed Charles     // does a std::unique_ptr::reset anyways.
75c26fbbfbSJakob Stoklund Olesen   }
76c26fbbfbSJakob Stoklund Olesen }
77c26fbbfbSJakob Stoklund Olesen 
78587e2741SMatthias Braun template <typename Callable>
79b7d3311cSBenjamin Kramer static bool foreachUnit(const TargetRegisterInfo *TRI,
80b7d3311cSBenjamin Kramer                         LiveInterval &VRegInterval, unsigned PhysReg,
81b7d3311cSBenjamin Kramer                         Callable Func) {
82587e2741SMatthias Braun   if (VRegInterval.hasSubRanges()) {
83587e2741SMatthias Braun     for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
84587e2741SMatthias Braun       unsigned Unit = (*Units).first;
85e6a2485eSMatthias Braun       LaneBitmask Mask = (*Units).second;
8609afa1eaSMatthias Braun       for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
87ea9f8ce0SKrzysztof Parzyszek         if ((S.LaneMask & Mask).any()) {
8809afa1eaSMatthias Braun           if (Func(Unit, S))
89587e2741SMatthias Braun             return true;
90587e2741SMatthias Braun           break;
91587e2741SMatthias Braun         }
92587e2741SMatthias Braun       }
93587e2741SMatthias Braun     }
94587e2741SMatthias Braun   } else {
95587e2741SMatthias Braun     for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
96587e2741SMatthias Braun       if (Func(*Units, VRegInterval))
97587e2741SMatthias Braun         return true;
98587e2741SMatthias Braun     }
99587e2741SMatthias Braun   }
100587e2741SMatthias Braun   return false;
101587e2741SMatthias Braun }
102587e2741SMatthias Braun 
103c26fbbfbSJakob Stoklund Olesen void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) {
104d34e60caSNicola Zaghen   LLVM_DEBUG(dbgs() << "assigning " << printReg(VirtReg.reg, TRI) << " to "
105d34e60caSNicola Zaghen                     << printReg(PhysReg, TRI) << ':');
106c26fbbfbSJakob Stoklund Olesen   assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
107c26fbbfbSJakob Stoklund Olesen   VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
108587e2741SMatthias Braun 
109d34e60caSNicola Zaghen   foreachUnit(
110d34e60caSNicola Zaghen       TRI, VirtReg, PhysReg, [&](unsigned Unit, const LiveRange &Range) {
111d34e60caSNicola Zaghen         LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << ' ' << Range);
112587e2741SMatthias Braun         Matrix[Unit].unify(VirtReg, Range);
113587e2741SMatthias Braun         return false;
114587e2741SMatthias Braun       });
115587e2741SMatthias Braun 
116c26fbbfbSJakob Stoklund Olesen   ++NumAssigned;
117d34e60caSNicola Zaghen   LLVM_DEBUG(dbgs() << '\n');
118c26fbbfbSJakob Stoklund Olesen }
119c26fbbfbSJakob Stoklund Olesen 
120c26fbbfbSJakob Stoklund Olesen void LiveRegMatrix::unassign(LiveInterval &VirtReg) {
121c26fbbfbSJakob Stoklund Olesen   unsigned PhysReg = VRM->getPhys(VirtReg.reg);
122d34e60caSNicola Zaghen   LLVM_DEBUG(dbgs() << "unassigning " << printReg(VirtReg.reg, TRI) << " from "
123d34e60caSNicola Zaghen                     << printReg(PhysReg, TRI) << ':');
124c26fbbfbSJakob Stoklund Olesen   VRM->clearVirt(VirtReg.reg);
125587e2741SMatthias Braun 
126d34e60caSNicola Zaghen   foreachUnit(TRI, VirtReg, PhysReg,
127d34e60caSNicola Zaghen               [&](unsigned Unit, const LiveRange &Range) {
128d34e60caSNicola Zaghen                 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI));
129587e2741SMatthias Braun                 Matrix[Unit].extract(VirtReg, Range);
130587e2741SMatthias Braun                 return false;
131587e2741SMatthias Braun               });
132587e2741SMatthias Braun 
133c26fbbfbSJakob Stoklund Olesen   ++NumUnassigned;
134d34e60caSNicola Zaghen   LLVM_DEBUG(dbgs() << '\n');
135c26fbbfbSJakob Stoklund Olesen }
136c26fbbfbSJakob Stoklund Olesen 
137953393a7SMatthias Braun bool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const {
138953393a7SMatthias Braun   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
139953393a7SMatthias Braun     if (!Matrix[*Unit].empty())
140953393a7SMatthias Braun       return true;
141953393a7SMatthias Braun   }
142953393a7SMatthias Braun   return false;
143953393a7SMatthias Braun }
144953393a7SMatthias Braun 
145c26fbbfbSJakob Stoklund Olesen bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg,
146c26fbbfbSJakob Stoklund Olesen                                              unsigned PhysReg) {
147c26fbbfbSJakob Stoklund Olesen   // Check if the cached information is valid.
148c26fbbfbSJakob Stoklund Olesen   // The same BitVector can be reused for all PhysRegs.
149c26fbbfbSJakob Stoklund Olesen   // We could cache multiple VirtRegs if it becomes necessary.
150c26fbbfbSJakob Stoklund Olesen   if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) {
151c26fbbfbSJakob Stoklund Olesen     RegMaskVirtReg = VirtReg.reg;
152c26fbbfbSJakob Stoklund Olesen     RegMaskTag = UserTag;
153c26fbbfbSJakob Stoklund Olesen     RegMaskUsable.clear();
154c26fbbfbSJakob Stoklund Olesen     LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
155c26fbbfbSJakob Stoklund Olesen   }
156c26fbbfbSJakob Stoklund Olesen 
157c26fbbfbSJakob Stoklund Olesen   // The BitVector is indexed by PhysReg, not register unit.
158c26fbbfbSJakob Stoklund Olesen   // Regmask interference is more fine grained than regunits.
159c26fbbfbSJakob Stoklund Olesen   // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
16013dffcb7SJakob Stoklund Olesen   return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg));
161c26fbbfbSJakob Stoklund Olesen }
162c26fbbfbSJakob Stoklund Olesen 
163c26fbbfbSJakob Stoklund Olesen bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg,
164c26fbbfbSJakob Stoklund Olesen                                              unsigned PhysReg) {
165c26fbbfbSJakob Stoklund Olesen   if (VirtReg.empty())
166c26fbbfbSJakob Stoklund Olesen     return false;
167866908c4SJakob Stoklund Olesen   CoalescerPair CP(VirtReg.reg, PhysReg, *TRI);
168587e2741SMatthias Braun 
169587e2741SMatthias Braun   bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
170587e2741SMatthias Braun                                                        const LiveRange &Range) {
171587e2741SMatthias Braun     const LiveRange &UnitRange = LIS->getRegUnit(Unit);
172587e2741SMatthias Braun     return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());
173587e2741SMatthias Braun   });
174587e2741SMatthias Braun   return Result;
175c26fbbfbSJakob Stoklund Olesen }
176c26fbbfbSJakob Stoklund Olesen 
177dbcf9e2eSMatthias Braun LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR,
178c26fbbfbSJakob Stoklund Olesen                                                unsigned RegUnit) {
179c26fbbfbSJakob Stoklund Olesen   LiveIntervalUnion::Query &Q = Queries[RegUnit];
180dbcf9e2eSMatthias Braun   Q.init(UserTag, LR, Matrix[RegUnit]);
181c26fbbfbSJakob Stoklund Olesen   return Q;
182c26fbbfbSJakob Stoklund Olesen }
183c26fbbfbSJakob Stoklund Olesen 
184c26fbbfbSJakob Stoklund Olesen LiveRegMatrix::InterferenceKind
185c26fbbfbSJakob Stoklund Olesen LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
186c26fbbfbSJakob Stoklund Olesen   if (VirtReg.empty())
187c26fbbfbSJakob Stoklund Olesen     return IK_Free;
188c26fbbfbSJakob Stoklund Olesen 
189c26fbbfbSJakob Stoklund Olesen   // Regmask interference is the fastest check.
190c26fbbfbSJakob Stoklund Olesen   if (checkRegMaskInterference(VirtReg, PhysReg))
191c26fbbfbSJakob Stoklund Olesen     return IK_RegMask;
192c26fbbfbSJakob Stoklund Olesen 
193c26fbbfbSJakob Stoklund Olesen   // Check for fixed interference.
194c26fbbfbSJakob Stoklund Olesen   if (checkRegUnitInterference(VirtReg, PhysReg))
195c26fbbfbSJakob Stoklund Olesen     return IK_RegUnit;
196c26fbbfbSJakob Stoklund Olesen 
197c26fbbfbSJakob Stoklund Olesen   // Check the matrix for virtual register interference.
198dbcf9e2eSMatthias Braun   bool Interference = foreachUnit(TRI, VirtReg, PhysReg,
199dbcf9e2eSMatthias Braun                                   [&](unsigned Unit, const LiveRange &LR) {
200dbcf9e2eSMatthias Braun     return query(LR, Unit).checkInterference();
201dbcf9e2eSMatthias Braun   });
202dbcf9e2eSMatthias Braun   if (Interference)
203c26fbbfbSJakob Stoklund Olesen     return IK_VirtReg;
204c26fbbfbSJakob Stoklund Olesen 
205c26fbbfbSJakob Stoklund Olesen   return IK_Free;
206c26fbbfbSJakob Stoklund Olesen }
207cd5bc4a2SMarina Yatsina 
208cd5bc4a2SMarina Yatsina bool LiveRegMatrix::checkInterference(SlotIndex Start, SlotIndex End,
209cd5bc4a2SMarina Yatsina                                       unsigned PhysReg) {
210cd5bc4a2SMarina Yatsina   // Construct artificial live range containing only one segment [Start, End).
211cd5bc4a2SMarina Yatsina   VNInfo valno(0, Start);
212cd5bc4a2SMarina Yatsina   LiveRange::Segment Seg(Start, End, &valno);
213cd5bc4a2SMarina Yatsina   LiveRange LR;
214cd5bc4a2SMarina Yatsina   LR.addSegment(Seg);
215cd5bc4a2SMarina Yatsina 
216cd5bc4a2SMarina Yatsina   // Check for interference with that segment
217cd5bc4a2SMarina Yatsina   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
218cd5bc4a2SMarina Yatsina     if (query(LR, *Units).checkInterference())
219cd5bc4a2SMarina Yatsina       return true;
220cd5bc4a2SMarina Yatsina   }
221cd5bc4a2SMarina Yatsina   return false;
222cd5bc4a2SMarina Yatsina }
223