303 lines · cpp
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-exception6//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 31using namespace llvm;32 33#define DEBUG_TYPE "regalloc"34 35STATISTIC(NumAssigned , "Number of registers assigned");36STATISTIC(NumUnassigned , "Number of registers unassigned");37 38char LiveRegMatrixWrapperLegacy::ID = 0;39INITIALIZE_PASS_BEGIN(LiveRegMatrixWrapperLegacy, "liveregmatrix",40 "Live Register Matrix", false, false)41INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)42INITIALIZE_PASS_DEPENDENCY(VirtRegMapWrapperLegacy)43INITIALIZE_PASS_END(LiveRegMatrixWrapperLegacy, "liveregmatrix",44 "Live Register Matrix", false, true)45 46void LiveRegMatrixWrapperLegacy::getAnalysisUsage(AnalysisUsage &AU) const {47 AU.setPreservesAll();48 AU.addRequiredTransitive<LiveIntervalsWrapperPass>();49 AU.addRequiredTransitive<VirtRegMapWrapperLegacy>();50 MachineFunctionPass::getAnalysisUsage(AU);51}52 53bool LiveRegMatrixWrapperLegacy::runOnMachineFunction(MachineFunction &MF) {54 auto &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();55 auto &VRM = getAnalysis<VirtRegMapWrapperLegacy>().getVRM();56 LRM.init(MF, LIS, VRM);57 return false;58}59 60void LiveRegMatrix::init(MachineFunction &MF, LiveIntervals &pLIS,61 VirtRegMap &pVRM) {62 TRI = MF.getSubtarget().getRegisterInfo();63 LIS = &pLIS;64 VRM = &pVRM;65 66 unsigned NumRegUnits = TRI->getNumRegUnits();67 if (NumRegUnits != Matrix.size())68 Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);69 Matrix.init(*LIUAlloc, NumRegUnits);70 71 // Make sure no stale queries get reused.72 invalidateVirtRegs();73}74 75void LiveRegMatrixWrapperLegacy::releaseMemory() { LRM.releaseMemory(); }76 77void LiveRegMatrix::releaseMemory() {78 for (unsigned i = 0, e = Matrix.size(); i != e; ++i) {79 Matrix[static_cast<MCRegUnit>(i)].clear();80 // No need to clear Queries here, since LiveIntervalUnion::Query doesn't81 // have anything important to clear and LiveRegMatrix's runOnFunction()82 // does a std::unique_ptr::reset anyways.83 }84}85 86template <typename Callable>87static bool foreachUnit(const TargetRegisterInfo *TRI,88 const LiveInterval &VRegInterval, MCRegister PhysReg,89 Callable Func) {90 if (VRegInterval.hasSubRanges()) {91 for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {92 MCRegUnit Unit = (*Units).first;93 LaneBitmask Mask = (*Units).second;94 for (const LiveInterval::SubRange &S : VRegInterval.subranges()) {95 if ((S.LaneMask & Mask).any()) {96 if (Func(Unit, S))97 return true;98 break;99 }100 }101 }102 } else {103 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {104 if (Func(Unit, VRegInterval))105 return true;106 }107 }108 return false;109}110 111void LiveRegMatrix::assign(const LiveInterval &VirtReg, MCRegister PhysReg) {112 LLVM_DEBUG(dbgs() << "assigning " << printReg(VirtReg.reg(), TRI) << " to "113 << printReg(PhysReg, TRI) << ':');114 assert(!VRM->hasPhys(VirtReg.reg()) && "Duplicate VirtReg assignment");115 VRM->assignVirt2Phys(VirtReg.reg(), PhysReg);116 117 foreachUnit(118 TRI, VirtReg, PhysReg, [&](MCRegUnit Unit, const LiveRange &Range) {119 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << ' ' << Range);120 Matrix[Unit].unify(VirtReg, Range);121 return false;122 });123 124 ++NumAssigned;125 LLVM_DEBUG(dbgs() << '\n');126}127 128void LiveRegMatrix::unassign(const LiveInterval &VirtReg) {129 Register PhysReg = VRM->getPhys(VirtReg.reg());130 LLVM_DEBUG(dbgs() << "unassigning " << printReg(VirtReg.reg(), TRI)131 << " from " << printReg(PhysReg, TRI) << ':');132 VRM->clearVirt(VirtReg.reg());133 134 foreachUnit(TRI, VirtReg, PhysReg,135 [&](MCRegUnit Unit, const LiveRange &Range) {136 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI));137 Matrix[Unit].extract(VirtReg, Range);138 return false;139 });140 141 ++NumUnassigned;142 LLVM_DEBUG(dbgs() << '\n');143}144 145bool LiveRegMatrix::isPhysRegUsed(MCRegister PhysReg) const {146 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {147 if (!Matrix[Unit].empty())148 return true;149 }150 return false;151}152 153bool LiveRegMatrix::checkRegMaskInterference(const LiveInterval &VirtReg,154 MCRegister PhysReg) {155 // Check if the cached information is valid.156 // The same BitVector can be reused for all PhysRegs.157 // We could cache multiple VirtRegs if it becomes necessary.158 if (RegMaskVirtReg != VirtReg.reg() || RegMaskTag != UserTag) {159 RegMaskVirtReg = VirtReg.reg();160 RegMaskTag = UserTag;161 RegMaskUsable.clear();162 LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);163 }164 165 // The BitVector is indexed by PhysReg, not register unit.166 // Regmask interference is more fine grained than regunits.167 // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.168 return !RegMaskUsable.empty() &&169 (!PhysReg || !RegMaskUsable.test(PhysReg.id()));170}171 172bool LiveRegMatrix::checkRegUnitInterference(const LiveInterval &VirtReg,173 MCRegister PhysReg) {174 if (VirtReg.empty())175 return false;176 CoalescerPair CP(VirtReg.reg(), PhysReg, *TRI);177 178 bool Result = foreachUnit(179 TRI, VirtReg, PhysReg, [&](MCRegUnit Unit, const LiveRange &Range) {180 const LiveRange &UnitRange = LIS->getRegUnit(Unit);181 return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());182 });183 return Result;184}185 186LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR,187 MCRegUnit RegUnit) {188 LiveIntervalUnion::Query &Q = Queries[static_cast<unsigned>(RegUnit)];189 Q.init(UserTag, LR, Matrix[RegUnit]);190 return Q;191}192 193LiveRegMatrix::InterferenceKind194LiveRegMatrix::checkInterference(const LiveInterval &VirtReg,195 MCRegister PhysReg) {196 if (VirtReg.empty())197 return IK_Free;198 199 // Regmask interference is the fastest check.200 if (checkRegMaskInterference(VirtReg, PhysReg))201 return IK_RegMask;202 203 // Check for fixed interference.204 if (checkRegUnitInterference(VirtReg, PhysReg))205 return IK_RegUnit;206 207 // Check the matrix for virtual register interference.208 bool Interference = foreachUnit(TRI, VirtReg, PhysReg,209 [&](MCRegUnit Unit, const LiveRange &LR) {210 return query(LR, Unit).checkInterference();211 });212 if (Interference)213 return IK_VirtReg;214 215 return IK_Free;216}217 218bool LiveRegMatrix::checkInterference(SlotIndex Start, SlotIndex End,219 MCRegister PhysReg) {220 // Construct artificial live range containing only one segment [Start, End).221 VNInfo valno(0, Start);222 LiveRange::Segment Seg(Start, End, &valno);223 LiveRange LR;224 LR.addSegment(Seg);225 226 // Check for interference with that segment227 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {228 // LR is stack-allocated. LiveRegMatrix caches queries by a key that229 // includes the address of the live range. If (for the same reg unit) this230 // checkInterference overload is called twice, without any other query()231 // calls in between (on heap-allocated LiveRanges) - which would invalidate232 // the cached query - the LR address seen the second time may well be the233 // same as that seen the first time, while the Start/End/valno may not - yet234 // the same cached result would be fetched. To avoid that, we don't cache235 // this query.236 //237 // FIXME: the usability of the Query API needs to be improved to avoid238 // subtle bugs due to query identity. Avoiding caching, for example, would239 // greatly simplify things.240 LiveIntervalUnion::Query Q;241 Q.reset(UserTag, LR, Matrix[Unit]);242 if (Q.checkInterference())243 return true;244 }245 return false;246}247 248LaneBitmask LiveRegMatrix::checkInterferenceLanes(SlotIndex Start,249 SlotIndex End,250 MCRegister PhysReg) {251 // Construct artificial live range containing only one segment [Start, End).252 VNInfo valno(0, Start);253 LiveRange::Segment Seg(Start, End, &valno);254 LiveRange LR;255 LR.addSegment(Seg);256 257 LaneBitmask InterferingLanes;258 259 // Check for interference with that segment260 for (MCRegUnitMaskIterator MCRU(PhysReg, TRI); MCRU.isValid(); ++MCRU) {261 auto [Unit, Lanes] = *MCRU;262 // LR is stack-allocated. LiveRegMatrix caches queries by a key that263 // includes the address of the live range. If (for the same reg unit) this264 // checkInterference overload is called twice, without any other query()265 // calls in between (on heap-allocated LiveRanges) - which would invalidate266 // the cached query - the LR address seen the second time may well be the267 // same as that seen the first time, while the Start/End/valno may not - yet268 // the same cached result would be fetched. To avoid that, we don't cache269 // this query.270 //271 // FIXME: the usability of the Query API needs to be improved to avoid272 // subtle bugs due to query identity. Avoiding caching, for example, would273 // greatly simplify things.274 LiveIntervalUnion::Query Q;275 Q.reset(UserTag, LR, Matrix[Unit]);276 if (Q.checkInterference())277 InterferingLanes |= Lanes;278 }279 280 return InterferingLanes;281}282 283Register LiveRegMatrix::getOneVReg(unsigned PhysReg) const {284 const LiveInterval *VRegInterval = nullptr;285 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {286 if ((VRegInterval = Matrix[Unit].getOneVReg()))287 return VRegInterval->reg();288 }289 290 return MCRegister::NoRegister;291}292 293AnalysisKey LiveRegMatrixAnalysis::Key;294 295LiveRegMatrix LiveRegMatrixAnalysis::run(MachineFunction &MF,296 MachineFunctionAnalysisManager &MFAM) {297 auto &LIS = MFAM.getResult<LiveIntervalsAnalysis>(MF);298 auto &VRM = MFAM.getResult<VirtRegMapAnalysis>(MF);299 LiveRegMatrix LRM;300 LRM.init(MF, LIS, VRM);301 return LRM;302}303