455 lines · cpp
1//===-- RenameIndependentSubregs.cpp - Live Interval Analysis -------------===//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/// Rename independent subregisters looks for virtual registers with10/// independently used subregisters and renames them to new virtual registers.11/// Example: In the following:12/// %0:sub0<read-undef> = ...13/// %0:sub1 = ...14/// use %0:sub015/// %0:sub0 = ...16/// use %0:sub017/// use %0:sub118/// sub0 and sub1 are never used together, and we have two independent sub019/// definitions. This pass will rename to:20/// %0:sub0<read-undef> = ...21/// %1:sub1<read-undef> = ...22/// use %1:sub123/// %2:sub1<read-undef> = ...24/// use %2:sub125/// use %0:sub026//27//===----------------------------------------------------------------------===//28 29#include "llvm/CodeGen/RenameIndependentSubregs.h"30#include "LiveRangeUtils.h"31#include "PHIEliminationUtils.h"32#include "llvm/CodeGen/LiveInterval.h"33#include "llvm/CodeGen/LiveIntervals.h"34#include "llvm/CodeGen/MachineFunctionPass.h"35#include "llvm/CodeGen/MachineInstrBuilder.h"36#include "llvm/CodeGen/MachineRegisterInfo.h"37#include "llvm/CodeGen/TargetInstrInfo.h"38#include "llvm/InitializePasses.h"39#include "llvm/Pass.h"40 41using namespace llvm;42 43#define DEBUG_TYPE "rename-independent-subregs"44 45namespace {46 47class RenameIndependentSubregs {48public:49 RenameIndependentSubregs(LiveIntervals *LIS) : LIS(LIS) {}50 51 bool run(MachineFunction &MF);52 53private:54 struct SubRangeInfo {55 ConnectedVNInfoEqClasses ConEQ;56 LiveInterval::SubRange *SR;57 unsigned Index;58 59 SubRangeInfo(LiveIntervals &LIS, LiveInterval::SubRange &SR,60 unsigned Index)61 : ConEQ(LIS), SR(&SR), Index(Index) {}62 };63 64 /// Split unrelated subregister components and rename them to new vregs.65 bool renameComponents(LiveInterval &LI) const;66 67 /// Build a vector of SubRange infos and a union find set of68 /// equivalence classes.69 /// Returns true if more than 1 equivalence class was found.70 bool findComponents(IntEqClasses &Classes,71 SmallVectorImpl<SubRangeInfo> &SubRangeInfos,72 LiveInterval &LI) const;73 74 /// Distribute the LiveInterval segments into the new LiveIntervals75 /// belonging to their class.76 void distribute(const IntEqClasses &Classes,77 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,78 const SmallVectorImpl<LiveInterval*> &Intervals) const;79 80 /// Constructs main liverange and add missing undef+dead flags.81 void computeMainRangesFixFlags(const IntEqClasses &Classes,82 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,83 const SmallVectorImpl<LiveInterval*> &Intervals) const;84 85 /// Rewrite Machine Operands to use the new vreg belonging to their class.86 void rewriteOperands(const IntEqClasses &Classes,87 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,88 const SmallVectorImpl<LiveInterval*> &Intervals) const;89 90 91 LiveIntervals *LIS = nullptr;92 MachineRegisterInfo *MRI = nullptr;93 const TargetInstrInfo *TII = nullptr;94};95 96class RenameIndependentSubregsLegacy : public MachineFunctionPass {97public:98 static char ID;99 RenameIndependentSubregsLegacy() : MachineFunctionPass(ID) {}100 bool runOnMachineFunction(MachineFunction &MF) override;101 StringRef getPassName() const override {102 return "Rename Disconnected Subregister Components";103 }104 105 void getAnalysisUsage(AnalysisUsage &AU) const override {106 AU.setPreservesCFG();107 AU.addRequired<LiveIntervalsWrapperPass>();108 AU.addPreserved<LiveIntervalsWrapperPass>();109 AU.addRequired<SlotIndexesWrapperPass>();110 AU.addPreserved<SlotIndexesWrapperPass>();111 MachineFunctionPass::getAnalysisUsage(AU);112 }113};114 115} // end anonymous namespace116 117char RenameIndependentSubregsLegacy::ID;118 119char &llvm::RenameIndependentSubregsID = RenameIndependentSubregsLegacy::ID;120 121INITIALIZE_PASS_BEGIN(RenameIndependentSubregsLegacy, DEBUG_TYPE,122 "Rename Independent Subregisters", false, false)123INITIALIZE_PASS_DEPENDENCY(SlotIndexesWrapperPass)124INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)125INITIALIZE_PASS_END(RenameIndependentSubregsLegacy, DEBUG_TYPE,126 "Rename Independent Subregisters", false, false)127 128bool RenameIndependentSubregs::renameComponents(LiveInterval &LI) const {129 // Shortcut: We cannot have split components with a single definition.130 if (LI.valnos.size() < 2)131 return false;132 133 SmallVector<SubRangeInfo, 4> SubRangeInfos;134 IntEqClasses Classes;135 if (!findComponents(Classes, SubRangeInfos, LI))136 return false;137 138 // Create a new VReg for each class.139 Register Reg = LI.reg();140 const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);141 SmallVector<LiveInterval*, 4> Intervals;142 Intervals.push_back(&LI);143 LLVM_DEBUG(dbgs() << printReg(Reg) << ": Found " << Classes.getNumClasses()144 << " equivalence classes.\n");145 LLVM_DEBUG(dbgs() << printReg(Reg) << ": Splitting into newly created:");146 for (unsigned I = 1, NumClasses = Classes.getNumClasses(); I < NumClasses;147 ++I) {148 Register NewVReg = MRI->createVirtualRegister(RegClass);149 LiveInterval &NewLI = LIS->createEmptyInterval(NewVReg);150 Intervals.push_back(&NewLI);151 LLVM_DEBUG(dbgs() << ' ' << printReg(NewVReg));152 }153 LLVM_DEBUG(dbgs() << '\n');154 155 rewriteOperands(Classes, SubRangeInfos, Intervals);156 distribute(Classes, SubRangeInfos, Intervals);157 computeMainRangesFixFlags(Classes, SubRangeInfos, Intervals);158 return true;159}160 161bool RenameIndependentSubregs::findComponents(IntEqClasses &Classes,162 SmallVectorImpl<RenameIndependentSubregs::SubRangeInfo> &SubRangeInfos,163 LiveInterval &LI) const {164 // First step: Create connected components for the VNInfos inside the165 // subranges and count the global number of such components.166 unsigned NumComponents = 0;167 for (LiveInterval::SubRange &SR : LI.subranges()) {168 SubRangeInfos.push_back(SubRangeInfo(*LIS, SR, NumComponents));169 ConnectedVNInfoEqClasses &ConEQ = SubRangeInfos.back().ConEQ;170 171 unsigned NumSubComponents = ConEQ.Classify(SR);172 NumComponents += NumSubComponents;173 }174 // Shortcut: With only 1 subrange, the normal separate component tests are175 // enough and we do not need to perform the union-find on the subregister176 // segments.177 if (SubRangeInfos.size() < 2)178 return false;179 180 // Next step: Build union-find structure over all subranges and merge classes181 // across subranges when they are affected by the same MachineOperand.182 const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();183 Classes.grow(NumComponents);184 Register Reg = LI.reg();185 for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {186 if (!MO.isDef() && !MO.readsReg())187 continue;188 unsigned SubRegIdx = MO.getSubReg();189 LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);190 unsigned MergedID = ~0u;191 for (RenameIndependentSubregs::SubRangeInfo &SRInfo : SubRangeInfos) {192 const LiveInterval::SubRange &SR = *SRInfo.SR;193 if ((SR.LaneMask & LaneMask).none())194 continue;195 SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());196 Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber())197 : Pos.getBaseIndex();198 const VNInfo *VNI = SR.getVNInfoAt(Pos);199 if (VNI == nullptr)200 continue;201 202 // Map to local representant ID.203 unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);204 // Global ID205 unsigned ID = LocalID + SRInfo.Index;206 // Merge other sets207 MergedID = MergedID == ~0u ? ID : Classes.join(MergedID, ID);208 }209 }210 211 // Early exit if we ended up with a single equivalence class.212 Classes.compress();213 unsigned NumClasses = Classes.getNumClasses();214 return NumClasses > 1;215}216 217void RenameIndependentSubregs::rewriteOperands(const IntEqClasses &Classes,218 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,219 const SmallVectorImpl<LiveInterval*> &Intervals) const {220 const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();221 Register Reg = Intervals[0]->reg();222 for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg),223 E = MRI->reg_nodbg_end(); I != E; ) {224 MachineOperand &MO = *I++;225 if (!MO.isDef() && !MO.readsReg())226 continue;227 228 auto *MI = MO.getParent();229 SlotIndex Pos = LIS->getInstructionIndex(*MI);230 Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber())231 : Pos.getBaseIndex();232 unsigned SubRegIdx = MO.getSubReg();233 LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);234 235 unsigned ID = ~0u;236 for (const SubRangeInfo &SRInfo : SubRangeInfos) {237 const LiveInterval::SubRange &SR = *SRInfo.SR;238 if ((SR.LaneMask & LaneMask).none())239 continue;240 const VNInfo *VNI = SR.getVNInfoAt(Pos);241 if (VNI == nullptr)242 continue;243 244 // Map to local representant ID.245 unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);246 // Global ID247 ID = Classes[LocalID + SRInfo.Index];248 break;249 }250 251 Register VReg = Intervals[ID]->reg();252 MO.setReg(VReg);253 254 if (MO.isTied() && Reg != VReg) {255 /// Undef use operands are not tracked in the equivalence class,256 /// but need to be updated if they are tied; take care to only257 /// update the tied operand.258 unsigned OperandNo = MO.getOperandNo();259 unsigned TiedIdx = MI->findTiedOperandIdx(OperandNo);260 MI->getOperand(TiedIdx).setReg(VReg);261 262 // above substitution breaks the iterator, so restart.263 I = MRI->reg_nodbg_begin(Reg);264 }265 }266 // TODO: We could attempt to recompute new register classes while visiting267 // the operands: Some of the split register may be fine with less constraint268 // classes than the original vreg.269}270 271void RenameIndependentSubregs::distribute(const IntEqClasses &Classes,272 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,273 const SmallVectorImpl<LiveInterval*> &Intervals) const {274 unsigned NumClasses = Classes.getNumClasses();275 SmallVector<unsigned, 8> VNIMapping;276 SmallVector<LiveInterval::SubRange*, 8> SubRanges;277 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();278 for (const SubRangeInfo &SRInfo : SubRangeInfos) {279 LiveInterval::SubRange &SR = *SRInfo.SR;280 unsigned NumValNos = SR.valnos.size();281 VNIMapping.clear();282 VNIMapping.reserve(NumValNos);283 SubRanges.clear();284 SubRanges.resize(NumClasses-1, nullptr);285 for (unsigned I = 0; I < NumValNos; ++I) {286 const VNInfo &VNI = *SR.valnos[I];287 unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI);288 unsigned ID = Classes[LocalID + SRInfo.Index];289 VNIMapping.push_back(ID);290 if (ID > 0 && SubRanges[ID-1] == nullptr)291 SubRanges[ID-1] = Intervals[ID]->createSubRange(Allocator, SR.LaneMask);292 }293 DistributeRange(SR, SubRanges.data(), VNIMapping);294 }295}296 297static bool subRangeLiveAt(const LiveInterval &LI, SlotIndex Pos) {298 for (const LiveInterval::SubRange &SR : LI.subranges()) {299 if (SR.liveAt(Pos))300 return true;301 }302 return false;303}304 305void RenameIndependentSubregs::computeMainRangesFixFlags(306 const IntEqClasses &Classes,307 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,308 const SmallVectorImpl<LiveInterval*> &Intervals) const {309 const TargetRegisterInfo &TRI = TII->getRegisterInfo();310 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();311 const SlotIndexes &Indexes = *LIS->getSlotIndexes();312 for (size_t I = 0, E = Intervals.size(); I < E; ++I) {313 LiveInterval &LI = *Intervals[I];314 Register Reg = LI.reg();315 316 LI.removeEmptySubRanges();317 318 // Try to establish a single subregister which covers all uses.319 // Note: this is assuming the selected subregister will only be320 // used for fixing up live intervals issues created by this pass.321 LaneBitmask UsedMask, UnusedMask;322 for (LiveInterval::SubRange &SR : LI.subranges())323 UsedMask |= SR.LaneMask;324 SmallVector<unsigned> SubRegIdxs;325 unsigned Flags = 0;326 unsigned SubReg = 0;327 // TODO: Handle SubRegIdxs.size() > 1328 if (TRI.getCoveringSubRegIndexes(MRI->getRegClass(Reg), UsedMask,329 SubRegIdxs) &&330 SubRegIdxs.size() == 1) {331 SubReg = SubRegIdxs.front();332 Flags = RegState::Undef;333 } else {334 UnusedMask = MRI->getMaxLaneMaskForVReg(Reg) & ~UsedMask;335 }336 337 // There must be a def (or live-in) before every use. Splitting vregs may338 // violate this principle as the splitted vreg may not have a definition on339 // every path. Fix this by creating IMPLICIT_DEF instruction as necessary.340 for (const LiveInterval::SubRange &SR : LI.subranges()) {341 // Search for "PHI" value numbers in the subranges. We must find a live342 // value in each predecessor block, add an IMPLICIT_DEF where it is343 // missing.344 for (unsigned I = 0; I < SR.valnos.size(); ++I) {345 const VNInfo &VNI = *SR.valnos[I];346 if (VNI.isUnused() || !VNI.isPHIDef())347 continue;348 349 SlotIndex Def = VNI.def;350 MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(Def);351 for (MachineBasicBlock *PredMBB : MBB.predecessors()) {352 SlotIndex PredEnd = Indexes.getMBBEndIdx(PredMBB);353 if (subRangeLiveAt(LI, PredEnd.getPrevSlot()))354 continue;355 356 MachineBasicBlock::iterator InsertPos =357 llvm::findPHICopyInsertPoint(PredMBB, &MBB, Reg);358 const MCInstrDesc &MCDesc = TII->get(TargetOpcode::IMPLICIT_DEF);359 MachineInstrBuilder ImpDef =360 BuildMI(*PredMBB, InsertPos, DebugLoc(), MCDesc)361 .addDef(Reg, Flags, SubReg);362 SlotIndex DefIdx = LIS->InsertMachineInstrInMaps(*ImpDef);363 SlotIndex RegDefIdx = DefIdx.getRegSlot();364 for (LiveInterval::SubRange &SR : LI.subranges()) {365 VNInfo *SRVNI = SR.getNextValue(RegDefIdx, Allocator);366 SR.addSegment(LiveRange::Segment(RegDefIdx, PredEnd, SRVNI));367 }368 if (!UnusedMask.none()) {369 LiveInterval::SubRange *SR =370 LI.createSubRange(Allocator, UnusedMask);371 SR->createDeadDef(RegDefIdx, Allocator);372 }373 }374 }375 }376 377 for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {378 if (!MO.isDef())379 continue;380 unsigned SubRegIdx = MO.getSubReg();381 if (SubRegIdx == 0)382 continue;383 // After assigning the new vreg we may not have any other sublanes living384 // in and out of the instruction anymore. We need to add new dead and385 // undef flags in these cases.386 if (!MO.isUndef()) {387 SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());388 if (!subRangeLiveAt(LI, Pos))389 MO.setIsUndef();390 }391 if (!MO.isDead()) {392 SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent()).getDeadSlot();393 if (!subRangeLiveAt(LI, Pos))394 MO.setIsDead();395 }396 }397 398 if (I == 0)399 LI.clear();400 LIS->constructMainRangeFromSubranges(LI);401 // A def of a subregister may be a use of other register lanes. Replacing402 // such a def with a def of a different register will eliminate the use,403 // and may cause the recorded live range to be larger than the actual404 // liveness in the program IR.405 LIS->shrinkToUses(&LI);406 }407}408 409PreservedAnalyses410RenameIndependentSubregsPass::run(MachineFunction &MF,411 MachineFunctionAnalysisManager &MFAM) {412 auto &LIS = MFAM.getResult<LiveIntervalsAnalysis>(MF);413 if (!RenameIndependentSubregs(&LIS).run(MF))414 return PreservedAnalyses::all();415 auto PA = getMachineFunctionPassPreservedAnalyses();416 PA.preserveSet<CFGAnalyses>();417 PA.preserve<LiveIntervalsAnalysis>();418 PA.preserve<SlotIndexesAnalysis>();419 return PA;420}421 422bool RenameIndependentSubregsLegacy::runOnMachineFunction(MachineFunction &MF) {423 auto &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();424 return RenameIndependentSubregs(&LIS).run(MF);425}426 427bool RenameIndependentSubregs::run(MachineFunction &MF) {428 // Skip renaming if liveness of subregister is not tracked.429 MRI = &MF.getRegInfo();430 if (!MRI->subRegLivenessEnabled())431 return false;432 433 LLVM_DEBUG(dbgs() << "Renaming independent subregister live ranges in "434 << MF.getName() << '\n');435 436 TII = MF.getSubtarget().getInstrInfo();437 438 // Iterate over all vregs. Note that we query getNumVirtRegs() the newly439 // created vregs end up with higher numbers but do not need to be visited as440 // there can't be any further splitting.441 bool Changed = false;442 for (size_t I = 0, E = MRI->getNumVirtRegs(); I < E; ++I) {443 Register Reg = Register::index2VirtReg(I);444 if (!LIS->hasInterval(Reg))445 continue;446 LiveInterval &LI = LIS->getInterval(Reg);447 if (!LI.hasSubRanges())448 continue;449 450 Changed |= renameComponents(LI);451 }452 453 return Changed;454}455