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