RenameIndependentSubregs.cpp revision 327952
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/// %0:sub0<read-undef> = ... 14/// %0:sub1 = ... 15/// use %0:sub0 16/// %0:sub0 = ... 17/// use %0:sub0 18/// use %0:sub1 19/// sub0 and sub1 are never used together, and we have two independent sub0 20/// definitions. This pass will rename to: 21/// %0:sub0<read-undef> = ... 22/// %1:sub1<read-undef> = ... 23/// use %1:sub1 24/// %2:sub1<read-undef> = ... 25/// use %2:sub1 26/// use %0:sub0 27// 28//===----------------------------------------------------------------------===// 29 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/Passes.h" 38#include "llvm/CodeGen/TargetInstrInfo.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, DEBUG_TYPE, 116 "Rename Independent Subregisters", false, false) 117INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 118INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 119INITIALIZE_PASS_END(RenameIndependentSubregs, DEBUG_TYPE, 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 if (MO.isTied() && Reg != VReg) { 248 /// Undef use operands are not tracked in the equivalence class but need 249 /// to be update if they are tied. 250 MO.getParent()->substituteRegister(Reg, VReg, 0, TRI); 251 252 // substituteRegister breaks the iterator, so restart. 253 I = MRI->reg_nodbg_begin(Reg); 254 } 255 } 256 // TODO: We could attempt to recompute new register classes while visiting 257 // the operands: Some of the split register may be fine with less constraint 258 // classes than the original vreg. 259} 260 261void RenameIndependentSubregs::distribute(const IntEqClasses &Classes, 262 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos, 263 const SmallVectorImpl<LiveInterval*> &Intervals) const { 264 unsigned NumClasses = Classes.getNumClasses(); 265 SmallVector<unsigned, 8> VNIMapping; 266 SmallVector<LiveInterval::SubRange*, 8> SubRanges; 267 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator(); 268 for (const SubRangeInfo &SRInfo : SubRangeInfos) { 269 LiveInterval::SubRange &SR = *SRInfo.SR; 270 unsigned NumValNos = SR.valnos.size(); 271 VNIMapping.clear(); 272 VNIMapping.reserve(NumValNos); 273 SubRanges.clear(); 274 SubRanges.resize(NumClasses-1, nullptr); 275 for (unsigned I = 0; I < NumValNos; ++I) { 276 const VNInfo &VNI = *SR.valnos[I]; 277 unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI); 278 unsigned ID = Classes[LocalID + SRInfo.Index]; 279 VNIMapping.push_back(ID); 280 if (ID > 0 && SubRanges[ID-1] == nullptr) 281 SubRanges[ID-1] = Intervals[ID]->createSubRange(Allocator, SR.LaneMask); 282 } 283 DistributeRange(SR, SubRanges.data(), VNIMapping); 284 } 285} 286 287static bool subRangeLiveAt(const LiveInterval &LI, SlotIndex Pos) { 288 for (const LiveInterval::SubRange &SR : LI.subranges()) { 289 if (SR.liveAt(Pos)) 290 return true; 291 } 292 return false; 293} 294 295void RenameIndependentSubregs::computeMainRangesFixFlags( 296 const IntEqClasses &Classes, 297 const SmallVectorImpl<SubRangeInfo> &SubRangeInfos, 298 const SmallVectorImpl<LiveInterval*> &Intervals) const { 299 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator(); 300 const SlotIndexes &Indexes = *LIS->getSlotIndexes(); 301 for (size_t I = 0, E = Intervals.size(); I < E; ++I) { 302 LiveInterval &LI = *Intervals[I]; 303 unsigned Reg = LI.reg; 304 305 LI.removeEmptySubRanges(); 306 307 // There must be a def (or live-in) before every use. Splitting vregs may 308 // violate this principle as the splitted vreg may not have a definition on 309 // every path. Fix this by creating IMPLICIT_DEF instruction as necessary. 310 for (const LiveInterval::SubRange &SR : LI.subranges()) { 311 // Search for "PHI" value numbers in the subranges. We must find a live 312 // value in each predecessor block, add an IMPLICIT_DEF where it is 313 // missing. 314 for (unsigned I = 0; I < SR.valnos.size(); ++I) { 315 const VNInfo &VNI = *SR.valnos[I]; 316 if (VNI.isUnused() || !VNI.isPHIDef()) 317 continue; 318 319 SlotIndex Def = VNI.def; 320 MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(Def); 321 for (MachineBasicBlock *PredMBB : MBB.predecessors()) { 322 SlotIndex PredEnd = Indexes.getMBBEndIdx(PredMBB); 323 if (subRangeLiveAt(LI, PredEnd.getPrevSlot())) 324 continue; 325 326 MachineBasicBlock::iterator InsertPos = 327 llvm::findPHICopyInsertPoint(PredMBB, &MBB, Reg); 328 const MCInstrDesc &MCDesc = TII->get(TargetOpcode::IMPLICIT_DEF); 329 MachineInstrBuilder ImpDef = BuildMI(*PredMBB, InsertPos, 330 DebugLoc(), MCDesc, Reg); 331 SlotIndex DefIdx = LIS->InsertMachineInstrInMaps(*ImpDef); 332 SlotIndex RegDefIdx = DefIdx.getRegSlot(); 333 for (LiveInterval::SubRange &SR : LI.subranges()) { 334 VNInfo *SRVNI = SR.getNextValue(RegDefIdx, Allocator); 335 SR.addSegment(LiveRange::Segment(RegDefIdx, PredEnd, SRVNI)); 336 } 337 } 338 } 339 } 340 341 for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) { 342 if (!MO.isDef()) 343 continue; 344 unsigned SubRegIdx = MO.getSubReg(); 345 if (SubRegIdx == 0) 346 continue; 347 // After assigning the new vreg we may not have any other sublanes living 348 // in and out of the instruction anymore. We need to add new dead and 349 // undef flags in these cases. 350 if (!MO.isUndef()) { 351 SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent()); 352 if (!subRangeLiveAt(LI, Pos)) 353 MO.setIsUndef(); 354 } 355 if (!MO.isDead()) { 356 SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent()).getDeadSlot(); 357 if (!subRangeLiveAt(LI, Pos)) 358 MO.setIsDead(); 359 } 360 } 361 362 if (I == 0) 363 LI.clear(); 364 LIS->constructMainRangeFromSubranges(LI); 365 // A def of a subregister may be a use of other register lanes. Replacing 366 // such a def with a def of a different register will eliminate the use, 367 // and may cause the recorded live range to be larger than the actual 368 // liveness in the program IR. 369 LIS->shrinkToUses(&LI); 370 } 371} 372 373bool RenameIndependentSubregs::runOnMachineFunction(MachineFunction &MF) { 374 // Skip renaming if liveness of subregister is not tracked. 375 MRI = &MF.getRegInfo(); 376 if (!MRI->subRegLivenessEnabled()) 377 return false; 378 379 DEBUG(dbgs() << "Renaming independent subregister live ranges in " 380 << MF.getName() << '\n'); 381 382 LIS = &getAnalysis<LiveIntervals>(); 383 TII = MF.getSubtarget().getInstrInfo(); 384 385 // Iterate over all vregs. Note that we query getNumVirtRegs() the newly 386 // created vregs end up with higher numbers but do not need to be visited as 387 // there can't be any further splitting. 388 bool Changed = false; 389 for (size_t I = 0, E = MRI->getNumVirtRegs(); I < E; ++I) { 390 unsigned Reg = TargetRegisterInfo::index2VirtReg(I); 391 if (!LIS->hasInterval(Reg)) 392 continue; 393 LiveInterval &LI = LIS->getInterval(Reg); 394 if (!LI.hasSubRanges()) 395 continue; 396 397 Changed |= renameComponents(LI); 398 } 399 400 return Changed; 401} 402