RenameIndependentSubregs.cpp revision 314564
1//===-- RenameIndependentSubregs.cpp - Live Interval Analysis -------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10/// Rename independent subregisters looks for virtual registers with 11/// independently used subregisters and renames them to new virtual registers. 12/// Example: In the following: 13/// %vreg0:sub0<read-undef> = ... 14/// %vreg0:sub1 = ... 15/// use %vreg0:sub0 16/// %vreg0:sub0 = ... 17/// use %vreg0:sub0 18/// use %vreg0:sub1 19/// sub0 and sub1 are never used together, and we have two independent sub0 20/// definitions. This pass will rename to: 21/// %vreg0:sub0<read-undef> = ... 22/// %vreg1:sub1<read-undef> = ... 23/// use %vreg1:sub1 24/// %vreg2:sub1<read-undef> = ... 25/// use %vreg2:sub1 26/// use %vreg0:sub0 27// 28//===----------------------------------------------------------------------===// 29 30#include "LiveRangeUtils.h" 31#include "PHIEliminationUtils.h" 32#include "llvm/CodeGen/LiveInterval.h" 33#include "llvm/CodeGen/LiveIntervalAnalysis.h" 34#include "llvm/CodeGen/MachineFunctionPass.h" 35#include "llvm/CodeGen/MachineRegisterInfo.h" 36#include "llvm/CodeGen/Passes.h" 37#include "llvm/Target/TargetInstrInfo.h" 38#include "llvm/CodeGen/MachineInstrBuilder.h" 39 40using namespace llvm; 41 42#define DEBUG_TYPE "rename-independent-subregs" 43 44namespace { 45 46class RenameIndependentSubregs : public MachineFunctionPass { 47public: 48 static char ID; 49 RenameIndependentSubregs() : MachineFunctionPass(ID) {} 50 51 StringRef getPassName() const override { 52 return "Rename Disconnected Subregister Components"; 53 } 54 55 void getAnalysisUsage(AnalysisUsage &AU) const override { 56 AU.setPreservesCFG(); 57 AU.addRequired<LiveIntervals>(); 58 AU.addPreserved<LiveIntervals>(); 59 AU.addRequired<SlotIndexes>(); 60 AU.addPreserved<SlotIndexes>(); 61 MachineFunctionPass::getAnalysisUsage(AU); 62 } 63 64 bool runOnMachineFunction(MachineFunction &MF) override; 65 66private: 67 struct SubRangeInfo { 68 ConnectedVNInfoEqClasses ConEQ; 69 LiveInterval::SubRange *SR; 70 unsigned Index; 71 72 SubRangeInfo(LiveIntervals &LIS, LiveInterval::SubRange &SR, 73 unsigned Index) 74 : ConEQ(LIS), SR(&SR), Index(Index) {} 75 }; 76 77 /// Split unrelated subregister components and rename them to new vregs. 78 bool renameComponents(LiveInterval &LI) const; 79 80 /// \brief Build a vector of SubRange infos and a union find set of 81 /// equivalence classes. 82 /// Returns true if more than 1 equivalence class was found. 83 bool findComponents(IntEqClasses &Classes, 84 SmallVectorImpl<SubRangeInfo> &SubRangeInfos, 85 LiveInterval &LI) const; 86 87 /// \brief Distribute the LiveInterval segments into the new LiveIntervals 88 /// belonging to their class. 89 void distribute(const IntEqClasses &Classes, 90 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos, 91 const SmallVectorImpl<LiveInterval*> &Intervals) const; 92 93 /// \brief Constructs main liverange and add missing undef+dead flags. 94 void computeMainRangesFixFlags(const IntEqClasses &Classes, 95 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos, 96 const SmallVectorImpl<LiveInterval*> &Intervals) const; 97 98 /// Rewrite Machine Operands to use the new vreg belonging to their class. 99 void rewriteOperands(const IntEqClasses &Classes, 100 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos, 101 const SmallVectorImpl<LiveInterval*> &Intervals) const; 102 103 104 LiveIntervals *LIS; 105 MachineRegisterInfo *MRI; 106 const TargetInstrInfo *TII; 107}; 108 109} // end anonymous namespace 110 111char RenameIndependentSubregs::ID; 112 113char &llvm::RenameIndependentSubregsID = RenameIndependentSubregs::ID; 114 115INITIALIZE_PASS_BEGIN(RenameIndependentSubregs, "rename-independent-subregs", 116 "Rename Independent Subregisters", false, false) 117INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 118INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 119INITIALIZE_PASS_END(RenameIndependentSubregs, "rename-independent-subregs", 120 "Rename Independent Subregisters", false, false) 121 122bool RenameIndependentSubregs::renameComponents(LiveInterval &LI) const { 123 // Shortcut: We cannot have split components with a single definition. 124 if (LI.valnos.size() < 2) 125 return false; 126 127 SmallVector<SubRangeInfo, 4> SubRangeInfos; 128 IntEqClasses Classes; 129 if (!findComponents(Classes, SubRangeInfos, LI)) 130 return false; 131 132 // Create a new VReg for each class. 133 unsigned Reg = LI.reg; 134 const TargetRegisterClass *RegClass = MRI->getRegClass(Reg); 135 SmallVector<LiveInterval*, 4> Intervals; 136 Intervals.push_back(&LI); 137 DEBUG(dbgs() << PrintReg(Reg) << ": Found " << Classes.getNumClasses() 138 << " equivalence classes.\n"); 139 DEBUG(dbgs() << PrintReg(Reg) << ": Splitting into newly created:"); 140 for (unsigned I = 1, NumClasses = Classes.getNumClasses(); I < NumClasses; 141 ++I) { 142 unsigned NewVReg = MRI->createVirtualRegister(RegClass); 143 LiveInterval &NewLI = LIS->createEmptyInterval(NewVReg); 144 Intervals.push_back(&NewLI); 145 DEBUG(dbgs() << ' ' << PrintReg(NewVReg)); 146 } 147 DEBUG(dbgs() << '\n'); 148 149 rewriteOperands(Classes, SubRangeInfos, Intervals); 150 distribute(Classes, SubRangeInfos, Intervals); 151 computeMainRangesFixFlags(Classes, SubRangeInfos, Intervals); 152 return true; 153} 154 155bool RenameIndependentSubregs::findComponents(IntEqClasses &Classes, 156 SmallVectorImpl<RenameIndependentSubregs::SubRangeInfo> &SubRangeInfos, 157 LiveInterval &LI) const { 158 // First step: Create connected components for the VNInfos inside the 159 // subranges and count the global number of such components. 160 unsigned NumComponents = 0; 161 for (LiveInterval::SubRange &SR : LI.subranges()) { 162 SubRangeInfos.push_back(SubRangeInfo(*LIS, SR, NumComponents)); 163 ConnectedVNInfoEqClasses &ConEQ = SubRangeInfos.back().ConEQ; 164 165 unsigned NumSubComponents = ConEQ.Classify(SR); 166 NumComponents += NumSubComponents; 167 } 168 // Shortcut: With only 1 subrange, the normal separate component tests are 169 // enough and we do not need to perform the union-find on the subregister 170 // segments. 171 if (SubRangeInfos.size() < 2) 172 return false; 173 174 // Next step: Build union-find structure over all subranges and merge classes 175 // across subranges when they are affected by the same MachineOperand. 176 const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo(); 177 Classes.grow(NumComponents); 178 unsigned Reg = LI.reg; 179 for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) { 180 if (!MO.isDef() && !MO.readsReg()) 181 continue; 182 unsigned SubRegIdx = MO.getSubReg(); 183 LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx); 184 unsigned MergedID = ~0u; 185 for (RenameIndependentSubregs::SubRangeInfo &SRInfo : SubRangeInfos) { 186 const LiveInterval::SubRange &SR = *SRInfo.SR; 187 if ((SR.LaneMask & LaneMask).none()) 188 continue; 189 SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent()); 190 Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber()) 191 : Pos.getBaseIndex(); 192 const VNInfo *VNI = SR.getVNInfoAt(Pos); 193 if (VNI == nullptr) 194 continue; 195 196 // Map to local representant ID. 197 unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI); 198 // Global ID 199 unsigned ID = LocalID + SRInfo.Index; 200 // Merge other sets 201 MergedID = MergedID == ~0u ? ID : Classes.join(MergedID, ID); 202 } 203 } 204 205 // Early exit if we ended up with a single equivalence class. 206 Classes.compress(); 207 unsigned NumClasses = Classes.getNumClasses(); 208 return NumClasses > 1; 209} 210 211void RenameIndependentSubregs::rewriteOperands(const IntEqClasses &Classes, 212 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos, 213 const SmallVectorImpl<LiveInterval*> &Intervals) const { 214 const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo(); 215 unsigned Reg = Intervals[0]->reg;; 216 for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg), 217 E = MRI->reg_nodbg_end(); I != E; ) { 218 MachineOperand &MO = *I++; 219 if (!MO.isDef() && !MO.readsReg()) 220 continue; 221 222 SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent()); 223 Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber()) 224 : Pos.getBaseIndex(); 225 unsigned SubRegIdx = MO.getSubReg(); 226 LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx); 227 228 unsigned ID = ~0u; 229 for (const SubRangeInfo &SRInfo : SubRangeInfos) { 230 const LiveInterval::SubRange &SR = *SRInfo.SR; 231 if ((SR.LaneMask & LaneMask).none()) 232 continue; 233 const VNInfo *VNI = SR.getVNInfoAt(Pos); 234 if (VNI == nullptr) 235 continue; 236 237 // Map to local representant ID. 238 unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI); 239 // Global ID 240 ID = Classes[LocalID + SRInfo.Index]; 241 break; 242 } 243 244 unsigned VReg = Intervals[ID]->reg; 245 MO.setReg(VReg); 246 } 247 // TODO: We could attempt to recompute new register classes while visiting 248 // the operands: Some of the split register may be fine with less constraint 249 // classes than the original vreg. 250} 251 252void RenameIndependentSubregs::distribute(const IntEqClasses &Classes, 253 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos, 254 const SmallVectorImpl<LiveInterval*> &Intervals) const { 255 unsigned NumClasses = Classes.getNumClasses(); 256 SmallVector<unsigned, 8> VNIMapping; 257 SmallVector<LiveInterval::SubRange*, 8> SubRanges; 258 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator(); 259 for (const SubRangeInfo &SRInfo : SubRangeInfos) { 260 LiveInterval::SubRange &SR = *SRInfo.SR; 261 unsigned NumValNos = SR.valnos.size(); 262 VNIMapping.clear(); 263 VNIMapping.reserve(NumValNos); 264 SubRanges.clear(); 265 SubRanges.resize(NumClasses-1, nullptr); 266 for (unsigned I = 0; I < NumValNos; ++I) { 267 const VNInfo &VNI = *SR.valnos[I]; 268 unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI); 269 unsigned ID = Classes[LocalID + SRInfo.Index]; 270 VNIMapping.push_back(ID); 271 if (ID > 0 && SubRanges[ID-1] == nullptr) 272 SubRanges[ID-1] = Intervals[ID]->createSubRange(Allocator, SR.LaneMask); 273 } 274 DistributeRange(SR, SubRanges.data(), VNIMapping); 275 } 276} 277 278static bool subRangeLiveAt(const LiveInterval &LI, SlotIndex Pos) { 279 for (const LiveInterval::SubRange &SR : LI.subranges()) { 280 if (SR.liveAt(Pos)) 281 return true; 282 } 283 return false; 284} 285 286void RenameIndependentSubregs::computeMainRangesFixFlags( 287 const IntEqClasses &Classes, 288 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos, 289 const SmallVectorImpl<LiveInterval*> &Intervals) const { 290 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator(); 291 const SlotIndexes &Indexes = *LIS->getSlotIndexes(); 292 for (size_t I = 0, E = Intervals.size(); I < E; ++I) { 293 LiveInterval &LI = *Intervals[I]; 294 unsigned Reg = LI.reg; 295 296 LI.removeEmptySubRanges(); 297 298 // There must be a def (or live-in) before every use. Splitting vregs may 299 // violate this principle as the splitted vreg may not have a definition on 300 // every path. Fix this by creating IMPLICIT_DEF instruction as necessary. 301 for (const LiveInterval::SubRange &SR : LI.subranges()) { 302 // Search for "PHI" value numbers in the subranges. We must find a live 303 // value in each predecessor block, add an IMPLICIT_DEF where it is 304 // missing. 305 for (unsigned I = 0; I < SR.valnos.size(); ++I) { 306 const VNInfo &VNI = *SR.valnos[I]; 307 if (VNI.isUnused() || !VNI.isPHIDef()) 308 continue; 309 310 SlotIndex Def = VNI.def; 311 MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(Def); 312 for (MachineBasicBlock *PredMBB : MBB.predecessors()) { 313 SlotIndex PredEnd = Indexes.getMBBEndIdx(PredMBB); 314 if (subRangeLiveAt(LI, PredEnd.getPrevSlot())) 315 continue; 316 317 MachineBasicBlock::iterator InsertPos = 318 llvm::findPHICopyInsertPoint(PredMBB, &MBB, Reg); 319 const MCInstrDesc &MCDesc = TII->get(TargetOpcode::IMPLICIT_DEF); 320 MachineInstrBuilder ImpDef = BuildMI(*PredMBB, InsertPos, 321 DebugLoc(), MCDesc, Reg); 322 SlotIndex DefIdx = LIS->InsertMachineInstrInMaps(*ImpDef); 323 SlotIndex RegDefIdx = DefIdx.getRegSlot(); 324 for (LiveInterval::SubRange &SR : LI.subranges()) { 325 VNInfo *SRVNI = SR.getNextValue(RegDefIdx, Allocator); 326 SR.addSegment(LiveRange::Segment(RegDefIdx, PredEnd, SRVNI)); 327 } 328 } 329 } 330 } 331 332 for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) { 333 if (!MO.isDef()) 334 continue; 335 unsigned SubRegIdx = MO.getSubReg(); 336 if (SubRegIdx == 0) 337 continue; 338 // After assigning the new vreg we may not have any other sublanes living 339 // in and out of the instruction anymore. We need to add new dead and 340 // undef flags in these cases. 341 if (!MO.isUndef()) { 342 SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent()); 343 if (!subRangeLiveAt(LI, Pos)) 344 MO.setIsUndef(); 345 } 346 if (!MO.isDead()) { 347 SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent()).getDeadSlot(); 348 if (!subRangeLiveAt(LI, Pos)) 349 MO.setIsDead(); 350 } 351 } 352 353 if (I == 0) 354 LI.clear(); 355 LIS->constructMainRangeFromSubranges(LI); 356 // A def of a subregister may be a use of other register lanes. Replacing 357 // such a def with a def of a different register will eliminate the use, 358 // and may cause the recorded live range to be larger than the actual 359 // liveness in the program IR. 360 LIS->shrinkToUses(&LI); 361 } 362} 363 364bool RenameIndependentSubregs::runOnMachineFunction(MachineFunction &MF) { 365 // Skip renaming if liveness of subregister is not tracked. 366 MRI = &MF.getRegInfo(); 367 if (!MRI->subRegLivenessEnabled()) 368 return false; 369 370 DEBUG(dbgs() << "Renaming independent subregister live ranges in " 371 << MF.getName() << '\n'); 372 373 LIS = &getAnalysis<LiveIntervals>(); 374 TII = MF.getSubtarget().getInstrInfo(); 375 376 // Iterate over all vregs. Note that we query getNumVirtRegs() the newly 377 // created vregs end up with higher numbers but do not need to be visited as 378 // there can't be any further splitting. 379 bool Changed = false; 380 for (size_t I = 0, E = MRI->getNumVirtRegs(); I < E; ++I) { 381 unsigned Reg = TargetRegisterInfo::index2VirtReg(I); 382 if (!LIS->hasInterval(Reg)) 383 continue; 384 LiveInterval &LI = LIS->getInterval(Reg); 385 if (!LI.hasSubRanges()) 386 continue; 387 388 Changed |= renameComponents(LI); 389 } 390 391 return Changed; 392} 393