RegisterCoalescer.cpp revision 314564
1//===- RegisterCoalescer.cpp - Generic Register Coalescing Interface -------==// 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// This file implements the generic RegisterCoalescer interface which 11// is used as the common interface used by all clients and 12// implementations of register coalescing. 13// 14//===----------------------------------------------------------------------===// 15 16#include "RegisterCoalescer.h" 17#include "llvm/ADT/STLExtras.h" 18#include "llvm/ADT/SmallSet.h" 19#include "llvm/ADT/Statistic.h" 20#include "llvm/Analysis/AliasAnalysis.h" 21#include "llvm/CodeGen/LiveIntervalAnalysis.h" 22#include "llvm/CodeGen/LiveRangeEdit.h" 23#include "llvm/CodeGen/MachineFrameInfo.h" 24#include "llvm/CodeGen/MachineInstr.h" 25#include "llvm/CodeGen/MachineLoopInfo.h" 26#include "llvm/CodeGen/MachineRegisterInfo.h" 27#include "llvm/CodeGen/Passes.h" 28#include "llvm/CodeGen/RegisterClassInfo.h" 29#include "llvm/CodeGen/VirtRegMap.h" 30#include "llvm/IR/Value.h" 31#include "llvm/Pass.h" 32#include "llvm/Support/CommandLine.h" 33#include "llvm/Support/Debug.h" 34#include "llvm/Support/ErrorHandling.h" 35#include "llvm/Support/raw_ostream.h" 36#include "llvm/Target/TargetInstrInfo.h" 37#include "llvm/Target/TargetMachine.h" 38#include "llvm/Target/TargetRegisterInfo.h" 39#include "llvm/Target/TargetSubtargetInfo.h" 40#include <algorithm> 41#include <cmath> 42using namespace llvm; 43 44#define DEBUG_TYPE "regalloc" 45 46STATISTIC(numJoins , "Number of interval joins performed"); 47STATISTIC(numCrossRCs , "Number of cross class joins performed"); 48STATISTIC(numCommutes , "Number of instruction commuting performed"); 49STATISTIC(numExtends , "Number of copies extended"); 50STATISTIC(NumReMats , "Number of instructions re-materialized"); 51STATISTIC(NumInflated , "Number of register classes inflated"); 52STATISTIC(NumLaneConflicts, "Number of dead lane conflicts tested"); 53STATISTIC(NumLaneResolves, "Number of dead lane conflicts resolved"); 54 55static cl::opt<bool> 56EnableJoining("join-liveintervals", 57 cl::desc("Coalesce copies (default=true)"), 58 cl::init(true)); 59 60static cl::opt<bool> UseTerminalRule("terminal-rule", 61 cl::desc("Apply the terminal rule"), 62 cl::init(false), cl::Hidden); 63 64/// Temporary flag to test critical edge unsplitting. 65static cl::opt<bool> 66EnableJoinSplits("join-splitedges", 67 cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden); 68 69/// Temporary flag to test global copy optimization. 70static cl::opt<cl::boolOrDefault> 71EnableGlobalCopies("join-globalcopies", 72 cl::desc("Coalesce copies that span blocks (default=subtarget)"), 73 cl::init(cl::BOU_UNSET), cl::Hidden); 74 75static cl::opt<bool> 76VerifyCoalescing("verify-coalescing", 77 cl::desc("Verify machine instrs before and after register coalescing"), 78 cl::Hidden); 79 80namespace { 81 class RegisterCoalescer : public MachineFunctionPass, 82 private LiveRangeEdit::Delegate { 83 MachineFunction* MF; 84 MachineRegisterInfo* MRI; 85 const TargetMachine* TM; 86 const TargetRegisterInfo* TRI; 87 const TargetInstrInfo* TII; 88 LiveIntervals *LIS; 89 const MachineLoopInfo* Loops; 90 AliasAnalysis *AA; 91 RegisterClassInfo RegClassInfo; 92 93 /// A LaneMask to remember on which subregister live ranges we need to call 94 /// shrinkToUses() later. 95 LaneBitmask ShrinkMask; 96 97 /// True if the main range of the currently coalesced intervals should be 98 /// checked for smaller live intervals. 99 bool ShrinkMainRange; 100 101 /// \brief True if the coalescer should aggressively coalesce global copies 102 /// in favor of keeping local copies. 103 bool JoinGlobalCopies; 104 105 /// \brief True if the coalescer should aggressively coalesce fall-thru 106 /// blocks exclusively containing copies. 107 bool JoinSplitEdges; 108 109 /// Copy instructions yet to be coalesced. 110 SmallVector<MachineInstr*, 8> WorkList; 111 SmallVector<MachineInstr*, 8> LocalWorkList; 112 113 /// Set of instruction pointers that have been erased, and 114 /// that may be present in WorkList. 115 SmallPtrSet<MachineInstr*, 8> ErasedInstrs; 116 117 /// Dead instructions that are about to be deleted. 118 SmallVector<MachineInstr*, 8> DeadDefs; 119 120 /// Virtual registers to be considered for register class inflation. 121 SmallVector<unsigned, 8> InflateRegs; 122 123 /// Recursively eliminate dead defs in DeadDefs. 124 void eliminateDeadDefs(); 125 126 /// LiveRangeEdit callback for eliminateDeadDefs(). 127 void LRE_WillEraseInstruction(MachineInstr *MI) override; 128 129 /// Coalesce the LocalWorkList. 130 void coalesceLocals(); 131 132 /// Join compatible live intervals 133 void joinAllIntervals(); 134 135 /// Coalesce copies in the specified MBB, putting 136 /// copies that cannot yet be coalesced into WorkList. 137 void copyCoalesceInMBB(MachineBasicBlock *MBB); 138 139 /// Tries to coalesce all copies in CurrList. Returns true if any progress 140 /// was made. 141 bool copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList); 142 143 /// Attempt to join intervals corresponding to SrcReg/DstReg, which are the 144 /// src/dst of the copy instruction CopyMI. This returns true if the copy 145 /// was successfully coalesced away. If it is not currently possible to 146 /// coalesce this interval, but it may be possible if other things get 147 /// coalesced, then it returns true by reference in 'Again'. 148 bool joinCopy(MachineInstr *TheCopy, bool &Again); 149 150 /// Attempt to join these two intervals. On failure, this 151 /// returns false. The output "SrcInt" will not have been modified, so we 152 /// can use this information below to update aliases. 153 bool joinIntervals(CoalescerPair &CP); 154 155 /// Attempt joining two virtual registers. Return true on success. 156 bool joinVirtRegs(CoalescerPair &CP); 157 158 /// Attempt joining with a reserved physreg. 159 bool joinReservedPhysReg(CoalescerPair &CP); 160 161 /// Add the LiveRange @p ToMerge as a subregister liverange of @p LI. 162 /// Subranges in @p LI which only partially interfere with the desired 163 /// LaneMask are split as necessary. @p LaneMask are the lanes that 164 /// @p ToMerge will occupy in the coalescer register. @p LI has its subrange 165 /// lanemasks already adjusted to the coalesced register. 166 void mergeSubRangeInto(LiveInterval &LI, const LiveRange &ToMerge, 167 LaneBitmask LaneMask, CoalescerPair &CP); 168 169 /// Join the liveranges of two subregisters. Joins @p RRange into 170 /// @p LRange, @p RRange may be invalid afterwards. 171 void joinSubRegRanges(LiveRange &LRange, LiveRange &RRange, 172 LaneBitmask LaneMask, const CoalescerPair &CP); 173 174 /// We found a non-trivially-coalescable copy. If the source value number is 175 /// defined by a copy from the destination reg see if we can merge these two 176 /// destination reg valno# into a single value number, eliminating a copy. 177 /// This returns true if an interval was modified. 178 bool adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI); 179 180 /// Return true if there are definitions of IntB 181 /// other than BValNo val# that can reach uses of AValno val# of IntA. 182 bool hasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB, 183 VNInfo *AValNo, VNInfo *BValNo); 184 185 /// We found a non-trivially-coalescable copy. 186 /// If the source value number is defined by a commutable instruction and 187 /// its other operand is coalesced to the copy dest register, see if we 188 /// can transform the copy into a noop by commuting the definition. 189 /// This returns true if an interval was modified. 190 bool removeCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI); 191 192 /// If the source of a copy is defined by a 193 /// trivial computation, replace the copy by rematerialize the definition. 194 bool reMaterializeTrivialDef(const CoalescerPair &CP, MachineInstr *CopyMI, 195 bool &IsDefCopy); 196 197 /// Return true if a copy involving a physreg should be joined. 198 bool canJoinPhys(const CoalescerPair &CP); 199 200 /// Replace all defs and uses of SrcReg to DstReg and update the subregister 201 /// number if it is not zero. If DstReg is a physical register and the 202 /// existing subregister number of the def / use being updated is not zero, 203 /// make sure to set it to the correct physical subregister. 204 void updateRegDefsUses(unsigned SrcReg, unsigned DstReg, unsigned SubIdx); 205 206 /// If the given machine operand reads only undefined lanes add an undef 207 /// flag. 208 /// This can happen when undef uses were previously concealed by a copy 209 /// which we coalesced. Example: 210 /// %vreg0:sub0<def,read-undef> = ... 211 /// %vreg1 = COPY %vreg0 <-- Coalescing COPY reveals undef 212 /// = use %vreg1:sub1 <-- hidden undef use 213 void addUndefFlag(const LiveInterval &Int, SlotIndex UseIdx, 214 MachineOperand &MO, unsigned SubRegIdx); 215 216 /// Handle copies of undef values. 217 /// Returns true if @p CopyMI was a copy of an undef value and eliminated. 218 bool eliminateUndefCopy(MachineInstr *CopyMI); 219 220 /// Check whether or not we should apply the terminal rule on the 221 /// destination (Dst) of \p Copy. 222 /// When the terminal rule applies, Copy is not profitable to 223 /// coalesce. 224 /// Dst is terminal if it has exactly one affinity (Dst, Src) and 225 /// at least one interference (Dst, Dst2). If Dst is terminal, the 226 /// terminal rule consists in checking that at least one of 227 /// interfering node, say Dst2, has an affinity of equal or greater 228 /// weight with Src. 229 /// In that case, Dst2 and Dst will not be able to be both coalesced 230 /// with Src. Since Dst2 exposes more coalescing opportunities than 231 /// Dst, we can drop \p Copy. 232 bool applyTerminalRule(const MachineInstr &Copy) const; 233 234 /// Wrapper method for \see LiveIntervals::shrinkToUses. 235 /// This method does the proper fixing of the live-ranges when the afore 236 /// mentioned method returns true. 237 void shrinkToUses(LiveInterval *LI, 238 SmallVectorImpl<MachineInstr * > *Dead = nullptr) { 239 if (LIS->shrinkToUses(LI, Dead)) { 240 /// Check whether or not \p LI is composed by multiple connected 241 /// components and if that is the case, fix that. 242 SmallVector<LiveInterval*, 8> SplitLIs; 243 LIS->splitSeparateComponents(*LI, SplitLIs); 244 } 245 } 246 247 public: 248 static char ID; ///< Class identification, replacement for typeinfo 249 RegisterCoalescer() : MachineFunctionPass(ID) { 250 initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 251 } 252 253 void getAnalysisUsage(AnalysisUsage &AU) const override; 254 255 void releaseMemory() override; 256 257 /// This is the pass entry point. 258 bool runOnMachineFunction(MachineFunction&) override; 259 260 /// Implement the dump method. 261 void print(raw_ostream &O, const Module* = nullptr) const override; 262 }; 263} // end anonymous namespace 264 265char &llvm::RegisterCoalescerID = RegisterCoalescer::ID; 266 267INITIALIZE_PASS_BEGIN(RegisterCoalescer, "simple-register-coalescing", 268 "Simple Register Coalescing", false, false) 269INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 270INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 271INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 272INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 273INITIALIZE_PASS_END(RegisterCoalescer, "simple-register-coalescing", 274 "Simple Register Coalescing", false, false) 275 276char RegisterCoalescer::ID = 0; 277 278static bool isMoveInstr(const TargetRegisterInfo &tri, const MachineInstr *MI, 279 unsigned &Src, unsigned &Dst, 280 unsigned &SrcSub, unsigned &DstSub) { 281 if (MI->isCopy()) { 282 Dst = MI->getOperand(0).getReg(); 283 DstSub = MI->getOperand(0).getSubReg(); 284 Src = MI->getOperand(1).getReg(); 285 SrcSub = MI->getOperand(1).getSubReg(); 286 } else if (MI->isSubregToReg()) { 287 Dst = MI->getOperand(0).getReg(); 288 DstSub = tri.composeSubRegIndices(MI->getOperand(0).getSubReg(), 289 MI->getOperand(3).getImm()); 290 Src = MI->getOperand(2).getReg(); 291 SrcSub = MI->getOperand(2).getSubReg(); 292 } else 293 return false; 294 return true; 295} 296 297/// Return true if this block should be vacated by the coalescer to eliminate 298/// branches. The important cases to handle in the coalescer are critical edges 299/// split during phi elimination which contain only copies. Simple blocks that 300/// contain non-branches should also be vacated, but this can be handled by an 301/// earlier pass similar to early if-conversion. 302static bool isSplitEdge(const MachineBasicBlock *MBB) { 303 if (MBB->pred_size() != 1 || MBB->succ_size() != 1) 304 return false; 305 306 for (const auto &MI : *MBB) { 307 if (!MI.isCopyLike() && !MI.isUnconditionalBranch()) 308 return false; 309 } 310 return true; 311} 312 313bool CoalescerPair::setRegisters(const MachineInstr *MI) { 314 SrcReg = DstReg = 0; 315 SrcIdx = DstIdx = 0; 316 NewRC = nullptr; 317 Flipped = CrossClass = false; 318 319 unsigned Src, Dst, SrcSub, DstSub; 320 if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 321 return false; 322 Partial = SrcSub || DstSub; 323 324 // If one register is a physreg, it must be Dst. 325 if (TargetRegisterInfo::isPhysicalRegister(Src)) { 326 if (TargetRegisterInfo::isPhysicalRegister(Dst)) 327 return false; 328 std::swap(Src, Dst); 329 std::swap(SrcSub, DstSub); 330 Flipped = true; 331 } 332 333 const MachineRegisterInfo &MRI = MI->getParent()->getParent()->getRegInfo(); 334 335 if (TargetRegisterInfo::isPhysicalRegister(Dst)) { 336 // Eliminate DstSub on a physreg. 337 if (DstSub) { 338 Dst = TRI.getSubReg(Dst, DstSub); 339 if (!Dst) return false; 340 DstSub = 0; 341 } 342 343 // Eliminate SrcSub by picking a corresponding Dst superregister. 344 if (SrcSub) { 345 Dst = TRI.getMatchingSuperReg(Dst, SrcSub, MRI.getRegClass(Src)); 346 if (!Dst) return false; 347 } else if (!MRI.getRegClass(Src)->contains(Dst)) { 348 return false; 349 } 350 } else { 351 // Both registers are virtual. 352 const TargetRegisterClass *SrcRC = MRI.getRegClass(Src); 353 const TargetRegisterClass *DstRC = MRI.getRegClass(Dst); 354 355 // Both registers have subreg indices. 356 if (SrcSub && DstSub) { 357 // Copies between different sub-registers are never coalescable. 358 if (Src == Dst && SrcSub != DstSub) 359 return false; 360 361 NewRC = TRI.getCommonSuperRegClass(SrcRC, SrcSub, DstRC, DstSub, 362 SrcIdx, DstIdx); 363 if (!NewRC) 364 return false; 365 } else if (DstSub) { 366 // SrcReg will be merged with a sub-register of DstReg. 367 SrcIdx = DstSub; 368 NewRC = TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub); 369 } else if (SrcSub) { 370 // DstReg will be merged with a sub-register of SrcReg. 371 DstIdx = SrcSub; 372 NewRC = TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSub); 373 } else { 374 // This is a straight copy without sub-registers. 375 NewRC = TRI.getCommonSubClass(DstRC, SrcRC); 376 } 377 378 // The combined constraint may be impossible to satisfy. 379 if (!NewRC) 380 return false; 381 382 // Prefer SrcReg to be a sub-register of DstReg. 383 // FIXME: Coalescer should support subregs symmetrically. 384 if (DstIdx && !SrcIdx) { 385 std::swap(Src, Dst); 386 std::swap(SrcIdx, DstIdx); 387 Flipped = !Flipped; 388 } 389 390 CrossClass = NewRC != DstRC || NewRC != SrcRC; 391 } 392 // Check our invariants 393 assert(TargetRegisterInfo::isVirtualRegister(Src) && "Src must be virtual"); 394 assert(!(TargetRegisterInfo::isPhysicalRegister(Dst) && DstSub) && 395 "Cannot have a physical SubIdx"); 396 SrcReg = Src; 397 DstReg = Dst; 398 return true; 399} 400 401bool CoalescerPair::flip() { 402 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) 403 return false; 404 std::swap(SrcReg, DstReg); 405 std::swap(SrcIdx, DstIdx); 406 Flipped = !Flipped; 407 return true; 408} 409 410bool CoalescerPair::isCoalescable(const MachineInstr *MI) const { 411 if (!MI) 412 return false; 413 unsigned Src, Dst, SrcSub, DstSub; 414 if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 415 return false; 416 417 // Find the virtual register that is SrcReg. 418 if (Dst == SrcReg) { 419 std::swap(Src, Dst); 420 std::swap(SrcSub, DstSub); 421 } else if (Src != SrcReg) { 422 return false; 423 } 424 425 // Now check that Dst matches DstReg. 426 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { 427 if (!TargetRegisterInfo::isPhysicalRegister(Dst)) 428 return false; 429 assert(!DstIdx && !SrcIdx && "Inconsistent CoalescerPair state."); 430 // DstSub could be set for a physreg from INSERT_SUBREG. 431 if (DstSub) 432 Dst = TRI.getSubReg(Dst, DstSub); 433 // Full copy of Src. 434 if (!SrcSub) 435 return DstReg == Dst; 436 // This is a partial register copy. Check that the parts match. 437 return TRI.getSubReg(DstReg, SrcSub) == Dst; 438 } else { 439 // DstReg is virtual. 440 if (DstReg != Dst) 441 return false; 442 // Registers match, do the subregisters line up? 443 return TRI.composeSubRegIndices(SrcIdx, SrcSub) == 444 TRI.composeSubRegIndices(DstIdx, DstSub); 445 } 446} 447 448void RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const { 449 AU.setPreservesCFG(); 450 AU.addRequired<AAResultsWrapperPass>(); 451 AU.addRequired<LiveIntervals>(); 452 AU.addPreserved<LiveIntervals>(); 453 AU.addPreserved<SlotIndexes>(); 454 AU.addRequired<MachineLoopInfo>(); 455 AU.addPreserved<MachineLoopInfo>(); 456 AU.addPreservedID(MachineDominatorsID); 457 MachineFunctionPass::getAnalysisUsage(AU); 458} 459 460void RegisterCoalescer::eliminateDeadDefs() { 461 SmallVector<unsigned, 8> NewRegs; 462 LiveRangeEdit(nullptr, NewRegs, *MF, *LIS, 463 nullptr, this).eliminateDeadDefs(DeadDefs); 464} 465 466void RegisterCoalescer::LRE_WillEraseInstruction(MachineInstr *MI) { 467 // MI may be in WorkList. Make sure we don't visit it. 468 ErasedInstrs.insert(MI); 469} 470 471bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP, 472 MachineInstr *CopyMI) { 473 assert(!CP.isPartial() && "This doesn't work for partial copies."); 474 assert(!CP.isPhys() && "This doesn't work for physreg copies."); 475 476 LiveInterval &IntA = 477 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 478 LiveInterval &IntB = 479 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 480 SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot(); 481 482 // We have a non-trivially-coalescable copy with IntA being the source and 483 // IntB being the dest, thus this defines a value number in IntB. If the 484 // source value number (in IntA) is defined by a copy from B, see if we can 485 // merge these two pieces of B into a single value number, eliminating a copy. 486 // For example: 487 // 488 // A3 = B0 489 // ... 490 // B1 = A3 <- this copy 491 // 492 // In this case, B0 can be extended to where the B1 copy lives, allowing the 493 // B1 value number to be replaced with B0 (which simplifies the B 494 // liveinterval). 495 496 // BValNo is a value number in B that is defined by a copy from A. 'B1' in 497 // the example above. 498 LiveInterval::iterator BS = IntB.FindSegmentContaining(CopyIdx); 499 if (BS == IntB.end()) return false; 500 VNInfo *BValNo = BS->valno; 501 502 // Get the location that B is defined at. Two options: either this value has 503 // an unknown definition point or it is defined at CopyIdx. If unknown, we 504 // can't process it. 505 if (BValNo->def != CopyIdx) return false; 506 507 // AValNo is the value number in A that defines the copy, A3 in the example. 508 SlotIndex CopyUseIdx = CopyIdx.getRegSlot(true); 509 LiveInterval::iterator AS = IntA.FindSegmentContaining(CopyUseIdx); 510 // The live segment might not exist after fun with physreg coalescing. 511 if (AS == IntA.end()) return false; 512 VNInfo *AValNo = AS->valno; 513 514 // If AValNo is defined as a copy from IntB, we can potentially process this. 515 // Get the instruction that defines this value number. 516 MachineInstr *ACopyMI = LIS->getInstructionFromIndex(AValNo->def); 517 // Don't allow any partial copies, even if isCoalescable() allows them. 518 if (!CP.isCoalescable(ACopyMI) || !ACopyMI->isFullCopy()) 519 return false; 520 521 // Get the Segment in IntB that this value number starts with. 522 LiveInterval::iterator ValS = 523 IntB.FindSegmentContaining(AValNo->def.getPrevSlot()); 524 if (ValS == IntB.end()) 525 return false; 526 527 // Make sure that the end of the live segment is inside the same block as 528 // CopyMI. 529 MachineInstr *ValSEndInst = 530 LIS->getInstructionFromIndex(ValS->end.getPrevSlot()); 531 if (!ValSEndInst || ValSEndInst->getParent() != CopyMI->getParent()) 532 return false; 533 534 // Okay, we now know that ValS ends in the same block that the CopyMI 535 // live-range starts. If there are no intervening live segments between them 536 // in IntB, we can merge them. 537 if (ValS+1 != BS) return false; 538 539 DEBUG(dbgs() << "Extending: " << PrintReg(IntB.reg, TRI)); 540 541 SlotIndex FillerStart = ValS->end, FillerEnd = BS->start; 542 // We are about to delete CopyMI, so need to remove it as the 'instruction 543 // that defines this value #'. Update the valnum with the new defining 544 // instruction #. 545 BValNo->def = FillerStart; 546 547 // Okay, we can merge them. We need to insert a new liverange: 548 // [ValS.end, BS.begin) of either value number, then we merge the 549 // two value numbers. 550 IntB.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, BValNo)); 551 552 // Okay, merge "B1" into the same value number as "B0". 553 if (BValNo != ValS->valno) 554 IntB.MergeValueNumberInto(BValNo, ValS->valno); 555 556 // Do the same for the subregister segments. 557 for (LiveInterval::SubRange &S : IntB.subranges()) { 558 VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx); 559 S.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, SubBValNo)); 560 VNInfo *SubValSNo = S.getVNInfoAt(AValNo->def.getPrevSlot()); 561 if (SubBValNo != SubValSNo) 562 S.MergeValueNumberInto(SubBValNo, SubValSNo); 563 } 564 565 DEBUG(dbgs() << " result = " << IntB << '\n'); 566 567 // If the source instruction was killing the source register before the 568 // merge, unset the isKill marker given the live range has been extended. 569 int UIdx = ValSEndInst->findRegisterUseOperandIdx(IntB.reg, true); 570 if (UIdx != -1) { 571 ValSEndInst->getOperand(UIdx).setIsKill(false); 572 } 573 574 // Rewrite the copy. If the copy instruction was killing the destination 575 // register before the merge, find the last use and trim the live range. That 576 // will also add the isKill marker. 577 CopyMI->substituteRegister(IntA.reg, IntB.reg, 0, *TRI); 578 if (AS->end == CopyIdx) 579 shrinkToUses(&IntA); 580 581 ++numExtends; 582 return true; 583} 584 585bool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA, 586 LiveInterval &IntB, 587 VNInfo *AValNo, 588 VNInfo *BValNo) { 589 // If AValNo has PHI kills, conservatively assume that IntB defs can reach 590 // the PHI values. 591 if (LIS->hasPHIKill(IntA, AValNo)) 592 return true; 593 594 for (LiveRange::Segment &ASeg : IntA.segments) { 595 if (ASeg.valno != AValNo) continue; 596 LiveInterval::iterator BI = 597 std::upper_bound(IntB.begin(), IntB.end(), ASeg.start); 598 if (BI != IntB.begin()) 599 --BI; 600 for (; BI != IntB.end() && ASeg.end >= BI->start; ++BI) { 601 if (BI->valno == BValNo) 602 continue; 603 if (BI->start <= ASeg.start && BI->end > ASeg.start) 604 return true; 605 if (BI->start > ASeg.start && BI->start < ASeg.end) 606 return true; 607 } 608 } 609 return false; 610} 611 612/// Copy segements with value number @p SrcValNo from liverange @p Src to live 613/// range @Dst and use value number @p DstValNo there. 614static void addSegmentsWithValNo(LiveRange &Dst, VNInfo *DstValNo, 615 const LiveRange &Src, const VNInfo *SrcValNo) 616{ 617 for (const LiveRange::Segment &S : Src.segments) { 618 if (S.valno != SrcValNo) 619 continue; 620 Dst.addSegment(LiveRange::Segment(S.start, S.end, DstValNo)); 621 } 622} 623 624bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, 625 MachineInstr *CopyMI) { 626 assert(!CP.isPhys()); 627 628 LiveInterval &IntA = 629 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 630 LiveInterval &IntB = 631 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 632 633 // We found a non-trivially-coalescable copy with IntA being the source and 634 // IntB being the dest, thus this defines a value number in IntB. If the 635 // source value number (in IntA) is defined by a commutable instruction and 636 // its other operand is coalesced to the copy dest register, see if we can 637 // transform the copy into a noop by commuting the definition. For example, 638 // 639 // A3 = op A2 B0<kill> 640 // ... 641 // B1 = A3 <- this copy 642 // ... 643 // = op A3 <- more uses 644 // 645 // ==> 646 // 647 // B2 = op B0 A2<kill> 648 // ... 649 // B1 = B2 <- now an identity copy 650 // ... 651 // = op B2 <- more uses 652 653 // BValNo is a value number in B that is defined by a copy from A. 'B1' in 654 // the example above. 655 SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot(); 656 VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx); 657 assert(BValNo != nullptr && BValNo->def == CopyIdx); 658 659 // AValNo is the value number in A that defines the copy, A3 in the example. 660 VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true)); 661 assert(AValNo && !AValNo->isUnused() && "COPY source not live"); 662 if (AValNo->isPHIDef()) 663 return false; 664 MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def); 665 if (!DefMI) 666 return false; 667 if (!DefMI->isCommutable()) 668 return false; 669 // If DefMI is a two-address instruction then commuting it will change the 670 // destination register. 671 int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg); 672 assert(DefIdx != -1); 673 unsigned UseOpIdx; 674 if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx)) 675 return false; 676 677 // FIXME: The code below tries to commute 'UseOpIdx' operand with some other 678 // commutable operand which is expressed by 'CommuteAnyOperandIndex'value 679 // passed to the method. That _other_ operand is chosen by 680 // the findCommutedOpIndices() method. 681 // 682 // That is obviously an area for improvement in case of instructions having 683 // more than 2 operands. For example, if some instruction has 3 commutable 684 // operands then all possible variants (i.e. op#1<->op#2, op#1<->op#3, 685 // op#2<->op#3) of commute transformation should be considered/tried here. 686 unsigned NewDstIdx = TargetInstrInfo::CommuteAnyOperandIndex; 687 if (!TII->findCommutedOpIndices(*DefMI, UseOpIdx, NewDstIdx)) 688 return false; 689 690 MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); 691 unsigned NewReg = NewDstMO.getReg(); 692 if (NewReg != IntB.reg || !IntB.Query(AValNo->def).isKill()) 693 return false; 694 695 // Make sure there are no other definitions of IntB that would reach the 696 // uses which the new definition can reach. 697 if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo)) 698 return false; 699 700 // If some of the uses of IntA.reg is already coalesced away, return false. 701 // It's not possible to determine whether it's safe to perform the coalescing. 702 for (MachineOperand &MO : MRI->use_nodbg_operands(IntA.reg)) { 703 MachineInstr *UseMI = MO.getParent(); 704 unsigned OpNo = &MO - &UseMI->getOperand(0); 705 SlotIndex UseIdx = LIS->getInstructionIndex(*UseMI); 706 LiveInterval::iterator US = IntA.FindSegmentContaining(UseIdx); 707 if (US == IntA.end() || US->valno != AValNo) 708 continue; 709 // If this use is tied to a def, we can't rewrite the register. 710 if (UseMI->isRegTiedToDefOperand(OpNo)) 711 return false; 712 } 713 714 DEBUG(dbgs() << "\tremoveCopyByCommutingDef: " << AValNo->def << '\t' 715 << *DefMI); 716 717 // At this point we have decided that it is legal to do this 718 // transformation. Start by commuting the instruction. 719 MachineBasicBlock *MBB = DefMI->getParent(); 720 MachineInstr *NewMI = 721 TII->commuteInstruction(*DefMI, false, UseOpIdx, NewDstIdx); 722 if (!NewMI) 723 return false; 724 if (TargetRegisterInfo::isVirtualRegister(IntA.reg) && 725 TargetRegisterInfo::isVirtualRegister(IntB.reg) && 726 !MRI->constrainRegClass(IntB.reg, MRI->getRegClass(IntA.reg))) 727 return false; 728 if (NewMI != DefMI) { 729 LIS->ReplaceMachineInstrInMaps(*DefMI, *NewMI); 730 MachineBasicBlock::iterator Pos = DefMI; 731 MBB->insert(Pos, NewMI); 732 MBB->erase(DefMI); 733 } 734 735 // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g. 736 // A = or A, B 737 // ... 738 // B = A 739 // ... 740 // C = A<kill> 741 // ... 742 // = B 743 744 // Update uses of IntA of the specific Val# with IntB. 745 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(IntA.reg), 746 UE = MRI->use_end(); 747 UI != UE; /* ++UI is below because of possible MI removal */) { 748 MachineOperand &UseMO = *UI; 749 ++UI; 750 if (UseMO.isUndef()) 751 continue; 752 MachineInstr *UseMI = UseMO.getParent(); 753 if (UseMI->isDebugValue()) { 754 // FIXME These don't have an instruction index. Not clear we have enough 755 // info to decide whether to do this replacement or not. For now do it. 756 UseMO.setReg(NewReg); 757 continue; 758 } 759 SlotIndex UseIdx = LIS->getInstructionIndex(*UseMI).getRegSlot(true); 760 LiveInterval::iterator US = IntA.FindSegmentContaining(UseIdx); 761 assert(US != IntA.end() && "Use must be live"); 762 if (US->valno != AValNo) 763 continue; 764 // Kill flags are no longer accurate. They are recomputed after RA. 765 UseMO.setIsKill(false); 766 if (TargetRegisterInfo::isPhysicalRegister(NewReg)) 767 UseMO.substPhysReg(NewReg, *TRI); 768 else 769 UseMO.setReg(NewReg); 770 if (UseMI == CopyMI) 771 continue; 772 if (!UseMI->isCopy()) 773 continue; 774 if (UseMI->getOperand(0).getReg() != IntB.reg || 775 UseMI->getOperand(0).getSubReg()) 776 continue; 777 778 // This copy will become a noop. If it's defining a new val#, merge it into 779 // BValNo. 780 SlotIndex DefIdx = UseIdx.getRegSlot(); 781 VNInfo *DVNI = IntB.getVNInfoAt(DefIdx); 782 if (!DVNI) 783 continue; 784 DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI); 785 assert(DVNI->def == DefIdx); 786 BValNo = IntB.MergeValueNumberInto(DVNI, BValNo); 787 for (LiveInterval::SubRange &S : IntB.subranges()) { 788 VNInfo *SubDVNI = S.getVNInfoAt(DefIdx); 789 if (!SubDVNI) 790 continue; 791 VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx); 792 assert(SubBValNo->def == CopyIdx); 793 S.MergeValueNumberInto(SubDVNI, SubBValNo); 794 } 795 796 ErasedInstrs.insert(UseMI); 797 LIS->RemoveMachineInstrFromMaps(*UseMI); 798 UseMI->eraseFromParent(); 799 } 800 801 // Extend BValNo by merging in IntA live segments of AValNo. Val# definition 802 // is updated. 803 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator(); 804 if (IntB.hasSubRanges()) { 805 if (!IntA.hasSubRanges()) { 806 LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(IntA.reg); 807 IntA.createSubRangeFrom(Allocator, Mask, IntA); 808 } 809 SlotIndex AIdx = CopyIdx.getRegSlot(true); 810 for (LiveInterval::SubRange &SA : IntA.subranges()) { 811 VNInfo *ASubValNo = SA.getVNInfoAt(AIdx); 812 assert(ASubValNo != nullptr); 813 814 LaneBitmask AMask = SA.LaneMask; 815 for (LiveInterval::SubRange &SB : IntB.subranges()) { 816 LaneBitmask BMask = SB.LaneMask; 817 LaneBitmask Common = BMask & AMask; 818 if (Common.none()) 819 continue; 820 821 DEBUG( dbgs() << "\t\tCopy_Merge " << PrintLaneMask(BMask) 822 << " into " << PrintLaneMask(Common) << '\n'); 823 LaneBitmask BRest = BMask & ~AMask; 824 LiveInterval::SubRange *CommonRange; 825 if (BRest.any()) { 826 SB.LaneMask = BRest; 827 DEBUG(dbgs() << "\t\tReduce Lane to " << PrintLaneMask(BRest) 828 << '\n'); 829 // Duplicate SubRange for newly merged common stuff. 830 CommonRange = IntB.createSubRangeFrom(Allocator, Common, SB); 831 } else { 832 // We van reuse the L SubRange. 833 SB.LaneMask = Common; 834 CommonRange = &SB; 835 } 836 LiveRange RangeCopy(SB, Allocator); 837 838 VNInfo *BSubValNo = CommonRange->getVNInfoAt(CopyIdx); 839 assert(BSubValNo->def == CopyIdx); 840 BSubValNo->def = ASubValNo->def; 841 addSegmentsWithValNo(*CommonRange, BSubValNo, SA, ASubValNo); 842 AMask &= ~BMask; 843 } 844 if (AMask.any()) { 845 DEBUG(dbgs() << "\t\tNew Lane " << PrintLaneMask(AMask) << '\n'); 846 LiveRange *NewRange = IntB.createSubRange(Allocator, AMask); 847 VNInfo *BSubValNo = NewRange->getNextValue(CopyIdx, Allocator); 848 addSegmentsWithValNo(*NewRange, BSubValNo, SA, ASubValNo); 849 } 850 } 851 } 852 853 BValNo->def = AValNo->def; 854 addSegmentsWithValNo(IntB, BValNo, IntA, AValNo); 855 DEBUG(dbgs() << "\t\textended: " << IntB << '\n'); 856 857 LIS->removeVRegDefAt(IntA, AValNo->def); 858 859 DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n'); 860 ++numCommutes; 861 return true; 862} 863 864/// Returns true if @p MI defines the full vreg @p Reg, as opposed to just 865/// defining a subregister. 866static bool definesFullReg(const MachineInstr &MI, unsigned Reg) { 867 assert(!TargetRegisterInfo::isPhysicalRegister(Reg) && 868 "This code cannot handle physreg aliasing"); 869 for (const MachineOperand &Op : MI.operands()) { 870 if (!Op.isReg() || !Op.isDef() || Op.getReg() != Reg) 871 continue; 872 // Return true if we define the full register or don't care about the value 873 // inside other subregisters. 874 if (Op.getSubReg() == 0 || Op.isUndef()) 875 return true; 876 } 877 return false; 878} 879 880bool RegisterCoalescer::reMaterializeTrivialDef(const CoalescerPair &CP, 881 MachineInstr *CopyMI, 882 bool &IsDefCopy) { 883 IsDefCopy = false; 884 unsigned SrcReg = CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg(); 885 unsigned SrcIdx = CP.isFlipped() ? CP.getDstIdx() : CP.getSrcIdx(); 886 unsigned DstReg = CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg(); 887 unsigned DstIdx = CP.isFlipped() ? CP.getSrcIdx() : CP.getDstIdx(); 888 if (TargetRegisterInfo::isPhysicalRegister(SrcReg)) 889 return false; 890 891 LiveInterval &SrcInt = LIS->getInterval(SrcReg); 892 SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI); 893 VNInfo *ValNo = SrcInt.Query(CopyIdx).valueIn(); 894 assert(ValNo && "CopyMI input register not live"); 895 if (ValNo->isPHIDef() || ValNo->isUnused()) 896 return false; 897 MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def); 898 if (!DefMI) 899 return false; 900 if (DefMI->isCopyLike()) { 901 IsDefCopy = true; 902 return false; 903 } 904 if (!TII->isAsCheapAsAMove(*DefMI)) 905 return false; 906 if (!TII->isTriviallyReMaterializable(*DefMI, AA)) 907 return false; 908 if (!definesFullReg(*DefMI, SrcReg)) 909 return false; 910 bool SawStore = false; 911 if (!DefMI->isSafeToMove(AA, SawStore)) 912 return false; 913 const MCInstrDesc &MCID = DefMI->getDesc(); 914 if (MCID.getNumDefs() != 1) 915 return false; 916 // Only support subregister destinations when the def is read-undef. 917 MachineOperand &DstOperand = CopyMI->getOperand(0); 918 unsigned CopyDstReg = DstOperand.getReg(); 919 if (DstOperand.getSubReg() && !DstOperand.isUndef()) 920 return false; 921 922 // If both SrcIdx and DstIdx are set, correct rematerialization would widen 923 // the register substantially (beyond both source and dest size). This is bad 924 // for performance since it can cascade through a function, introducing many 925 // extra spills and fills (e.g. ARM can easily end up copying QQQQPR registers 926 // around after a few subreg copies). 927 if (SrcIdx && DstIdx) 928 return false; 929 930 const TargetRegisterClass *DefRC = TII->getRegClass(MCID, 0, TRI, *MF); 931 if (!DefMI->isImplicitDef()) { 932 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { 933 unsigned NewDstReg = DstReg; 934 935 unsigned NewDstIdx = TRI->composeSubRegIndices(CP.getSrcIdx(), 936 DefMI->getOperand(0).getSubReg()); 937 if (NewDstIdx) 938 NewDstReg = TRI->getSubReg(DstReg, NewDstIdx); 939 940 // Finally, make sure that the physical subregister that will be 941 // constructed later is permitted for the instruction. 942 if (!DefRC->contains(NewDstReg)) 943 return false; 944 } else { 945 // Theoretically, some stack frame reference could exist. Just make sure 946 // it hasn't actually happened. 947 assert(TargetRegisterInfo::isVirtualRegister(DstReg) && 948 "Only expect to deal with virtual or physical registers"); 949 } 950 } 951 952 DebugLoc DL = CopyMI->getDebugLoc(); 953 MachineBasicBlock *MBB = CopyMI->getParent(); 954 MachineBasicBlock::iterator MII = 955 std::next(MachineBasicBlock::iterator(CopyMI)); 956 TII->reMaterialize(*MBB, MII, DstReg, SrcIdx, *DefMI, *TRI); 957 MachineInstr &NewMI = *std::prev(MII); 958 NewMI.setDebugLoc(DL); 959 960 // In a situation like the following: 961 // %vreg0:subreg = instr ; DefMI, subreg = DstIdx 962 // %vreg1 = copy %vreg0:subreg ; CopyMI, SrcIdx = 0 963 // instead of widening %vreg1 to the register class of %vreg0 simply do: 964 // %vreg1 = instr 965 const TargetRegisterClass *NewRC = CP.getNewRC(); 966 if (DstIdx != 0) { 967 MachineOperand &DefMO = NewMI.getOperand(0); 968 if (DefMO.getSubReg() == DstIdx) { 969 assert(SrcIdx == 0 && CP.isFlipped() 970 && "Shouldn't have SrcIdx+DstIdx at this point"); 971 const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg); 972 const TargetRegisterClass *CommonRC = 973 TRI->getCommonSubClass(DefRC, DstRC); 974 if (CommonRC != nullptr) { 975 NewRC = CommonRC; 976 DstIdx = 0; 977 DefMO.setSubReg(0); 978 DefMO.setIsUndef(false); // Only subregs can have def+undef. 979 } 980 } 981 } 982 983 // CopyMI may have implicit operands, save them so that we can transfer them 984 // over to the newly materialized instruction after CopyMI is removed. 985 SmallVector<MachineOperand, 4> ImplicitOps; 986 ImplicitOps.reserve(CopyMI->getNumOperands() - 987 CopyMI->getDesc().getNumOperands()); 988 for (unsigned I = CopyMI->getDesc().getNumOperands(), 989 E = CopyMI->getNumOperands(); 990 I != E; ++I) { 991 MachineOperand &MO = CopyMI->getOperand(I); 992 if (MO.isReg()) { 993 assert(MO.isImplicit() && "No explicit operands after implict operands."); 994 // Discard VReg implicit defs. 995 if (TargetRegisterInfo::isPhysicalRegister(MO.getReg())) 996 ImplicitOps.push_back(MO); 997 } 998 } 999 1000 LIS->ReplaceMachineInstrInMaps(*CopyMI, NewMI); 1001 CopyMI->eraseFromParent(); 1002 ErasedInstrs.insert(CopyMI); 1003 1004 // NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86). 1005 // We need to remember these so we can add intervals once we insert 1006 // NewMI into SlotIndexes. 1007 SmallVector<unsigned, 4> NewMIImplDefs; 1008 for (unsigned i = NewMI.getDesc().getNumOperands(), 1009 e = NewMI.getNumOperands(); 1010 i != e; ++i) { 1011 MachineOperand &MO = NewMI.getOperand(i); 1012 if (MO.isReg() && MO.isDef()) { 1013 assert(MO.isImplicit() && MO.isDead() && 1014 TargetRegisterInfo::isPhysicalRegister(MO.getReg())); 1015 NewMIImplDefs.push_back(MO.getReg()); 1016 } 1017 } 1018 1019 if (TargetRegisterInfo::isVirtualRegister(DstReg)) { 1020 unsigned NewIdx = NewMI.getOperand(0).getSubReg(); 1021 1022 if (DefRC != nullptr) { 1023 if (NewIdx) 1024 NewRC = TRI->getMatchingSuperRegClass(NewRC, DefRC, NewIdx); 1025 else 1026 NewRC = TRI->getCommonSubClass(NewRC, DefRC); 1027 assert(NewRC && "subreg chosen for remat incompatible with instruction"); 1028 } 1029 // Remap subranges to new lanemask and change register class. 1030 LiveInterval &DstInt = LIS->getInterval(DstReg); 1031 for (LiveInterval::SubRange &SR : DstInt.subranges()) { 1032 SR.LaneMask = TRI->composeSubRegIndexLaneMask(DstIdx, SR.LaneMask); 1033 } 1034 MRI->setRegClass(DstReg, NewRC); 1035 1036 // Update machine operands and add flags. 1037 updateRegDefsUses(DstReg, DstReg, DstIdx); 1038 NewMI.getOperand(0).setSubReg(NewIdx); 1039 // Add dead subregister definitions if we are defining the whole register 1040 // but only part of it is live. 1041 // This could happen if the rematerialization instruction is rematerializing 1042 // more than actually is used in the register. 1043 // An example would be: 1044 // vreg1 = LOAD CONSTANTS 5, 8 ; Loading both 5 and 8 in different subregs 1045 // ; Copying only part of the register here, but the rest is undef. 1046 // vreg2:sub_16bit<def, read-undef> = COPY vreg1:sub_16bit 1047 // ==> 1048 // ; Materialize all the constants but only using one 1049 // vreg2 = LOAD_CONSTANTS 5, 8 1050 // 1051 // at this point for the part that wasn't defined before we could have 1052 // subranges missing the definition. 1053 if (NewIdx == 0 && DstInt.hasSubRanges()) { 1054 SlotIndex CurrIdx = LIS->getInstructionIndex(NewMI); 1055 SlotIndex DefIndex = 1056 CurrIdx.getRegSlot(NewMI.getOperand(0).isEarlyClobber()); 1057 LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(DstReg); 1058 VNInfo::Allocator& Alloc = LIS->getVNInfoAllocator(); 1059 for (LiveInterval::SubRange &SR : DstInt.subranges()) { 1060 if (!SR.liveAt(DefIndex)) 1061 SR.createDeadDef(DefIndex, Alloc); 1062 MaxMask &= ~SR.LaneMask; 1063 } 1064 if (MaxMask.any()) { 1065 LiveInterval::SubRange *SR = DstInt.createSubRange(Alloc, MaxMask); 1066 SR->createDeadDef(DefIndex, Alloc); 1067 } 1068 } 1069 } else if (NewMI.getOperand(0).getReg() != CopyDstReg) { 1070 // The New instruction may be defining a sub-register of what's actually 1071 // been asked for. If so it must implicitly define the whole thing. 1072 assert(TargetRegisterInfo::isPhysicalRegister(DstReg) && 1073 "Only expect virtual or physical registers in remat"); 1074 NewMI.getOperand(0).setIsDead(true); 1075 NewMI.addOperand(MachineOperand::CreateReg( 1076 CopyDstReg, true /*IsDef*/, true /*IsImp*/, false /*IsKill*/)); 1077 // Record small dead def live-ranges for all the subregisters 1078 // of the destination register. 1079 // Otherwise, variables that live through may miss some 1080 // interferences, thus creating invalid allocation. 1081 // E.g., i386 code: 1082 // vreg1 = somedef ; vreg1 GR8 1083 // vreg2 = remat ; vreg2 GR32 1084 // CL = COPY vreg2.sub_8bit 1085 // = somedef vreg1 ; vreg1 GR8 1086 // => 1087 // vreg1 = somedef ; vreg1 GR8 1088 // ECX<def, dead> = remat ; CL<imp-def> 1089 // = somedef vreg1 ; vreg1 GR8 1090 // vreg1 will see the inteferences with CL but not with CH since 1091 // no live-ranges would have been created for ECX. 1092 // Fix that! 1093 SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI); 1094 for (MCRegUnitIterator Units(NewMI.getOperand(0).getReg(), TRI); 1095 Units.isValid(); ++Units) 1096 if (LiveRange *LR = LIS->getCachedRegUnit(*Units)) 1097 LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator()); 1098 } 1099 1100 if (NewMI.getOperand(0).getSubReg()) 1101 NewMI.getOperand(0).setIsUndef(); 1102 1103 // Transfer over implicit operands to the rematerialized instruction. 1104 for (MachineOperand &MO : ImplicitOps) 1105 NewMI.addOperand(MO); 1106 1107 SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI); 1108 for (unsigned i = 0, e = NewMIImplDefs.size(); i != e; ++i) { 1109 unsigned Reg = NewMIImplDefs[i]; 1110 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) 1111 if (LiveRange *LR = LIS->getCachedRegUnit(*Units)) 1112 LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator()); 1113 } 1114 1115 DEBUG(dbgs() << "Remat: " << NewMI); 1116 ++NumReMats; 1117 1118 // The source interval can become smaller because we removed a use. 1119 shrinkToUses(&SrcInt, &DeadDefs); 1120 if (!DeadDefs.empty()) { 1121 // If the virtual SrcReg is completely eliminated, update all DBG_VALUEs 1122 // to describe DstReg instead. 1123 for (MachineOperand &UseMO : MRI->use_operands(SrcReg)) { 1124 MachineInstr *UseMI = UseMO.getParent(); 1125 if (UseMI->isDebugValue()) { 1126 UseMO.setReg(DstReg); 1127 DEBUG(dbgs() << "\t\tupdated: " << *UseMI); 1128 } 1129 } 1130 eliminateDeadDefs(); 1131 } 1132 1133 return true; 1134} 1135 1136bool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI) { 1137 // ProcessImpicitDefs may leave some copies of <undef> values, it only removes 1138 // local variables. When we have a copy like: 1139 // 1140 // %vreg1 = COPY %vreg2<undef> 1141 // 1142 // We delete the copy and remove the corresponding value number from %vreg1. 1143 // Any uses of that value number are marked as <undef>. 1144 1145 // Note that we do not query CoalescerPair here but redo isMoveInstr as the 1146 // CoalescerPair may have a new register class with adjusted subreg indices 1147 // at this point. 1148 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; 1149 isMoveInstr(*TRI, CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx); 1150 1151 SlotIndex Idx = LIS->getInstructionIndex(*CopyMI); 1152 const LiveInterval &SrcLI = LIS->getInterval(SrcReg); 1153 // CopyMI is undef iff SrcReg is not live before the instruction. 1154 if (SrcSubIdx != 0 && SrcLI.hasSubRanges()) { 1155 LaneBitmask SrcMask = TRI->getSubRegIndexLaneMask(SrcSubIdx); 1156 for (const LiveInterval::SubRange &SR : SrcLI.subranges()) { 1157 if ((SR.LaneMask & SrcMask).none()) 1158 continue; 1159 if (SR.liveAt(Idx)) 1160 return false; 1161 } 1162 } else if (SrcLI.liveAt(Idx)) 1163 return false; 1164 1165 DEBUG(dbgs() << "\tEliminating copy of <undef> value\n"); 1166 1167 // Remove any DstReg segments starting at the instruction. 1168 LiveInterval &DstLI = LIS->getInterval(DstReg); 1169 SlotIndex RegIndex = Idx.getRegSlot(); 1170 // Remove value or merge with previous one in case of a subregister def. 1171 if (VNInfo *PrevVNI = DstLI.getVNInfoAt(Idx)) { 1172 VNInfo *VNI = DstLI.getVNInfoAt(RegIndex); 1173 DstLI.MergeValueNumberInto(VNI, PrevVNI); 1174 1175 // The affected subregister segments can be removed. 1176 LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(DstSubIdx); 1177 for (LiveInterval::SubRange &SR : DstLI.subranges()) { 1178 if ((SR.LaneMask & DstMask).none()) 1179 continue; 1180 1181 VNInfo *SVNI = SR.getVNInfoAt(RegIndex); 1182 assert(SVNI != nullptr && SlotIndex::isSameInstr(SVNI->def, RegIndex)); 1183 SR.removeValNo(SVNI); 1184 } 1185 DstLI.removeEmptySubRanges(); 1186 } else 1187 LIS->removeVRegDefAt(DstLI, RegIndex); 1188 1189 // Mark uses as undef. 1190 for (MachineOperand &MO : MRI->reg_nodbg_operands(DstReg)) { 1191 if (MO.isDef() /*|| MO.isUndef()*/) 1192 continue; 1193 const MachineInstr &MI = *MO.getParent(); 1194 SlotIndex UseIdx = LIS->getInstructionIndex(MI); 1195 LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg()); 1196 bool isLive; 1197 if (!UseMask.all() && DstLI.hasSubRanges()) { 1198 isLive = false; 1199 for (const LiveInterval::SubRange &SR : DstLI.subranges()) { 1200 if ((SR.LaneMask & UseMask).none()) 1201 continue; 1202 if (SR.liveAt(UseIdx)) { 1203 isLive = true; 1204 break; 1205 } 1206 } 1207 } else 1208 isLive = DstLI.liveAt(UseIdx); 1209 if (isLive) 1210 continue; 1211 MO.setIsUndef(true); 1212 DEBUG(dbgs() << "\tnew undef: " << UseIdx << '\t' << MI); 1213 } 1214 1215 // A def of a subregister may be a use of the other subregisters, so 1216 // deleting a def of a subregister may also remove uses. Since CopyMI 1217 // is still part of the function (but about to be erased), mark all 1218 // defs of DstReg in it as <undef>, so that shrinkToUses would 1219 // ignore them. 1220 for (MachineOperand &MO : CopyMI->operands()) 1221 if (MO.isReg() && MO.isDef() && MO.getReg() == DstReg) 1222 MO.setIsUndef(true); 1223 LIS->shrinkToUses(&DstLI); 1224 1225 return true; 1226} 1227 1228void RegisterCoalescer::addUndefFlag(const LiveInterval &Int, SlotIndex UseIdx, 1229 MachineOperand &MO, unsigned SubRegIdx) { 1230 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubRegIdx); 1231 if (MO.isDef()) 1232 Mask = ~Mask; 1233 bool IsUndef = true; 1234 for (const LiveInterval::SubRange &S : Int.subranges()) { 1235 if ((S.LaneMask & Mask).none()) 1236 continue; 1237 if (S.liveAt(UseIdx)) { 1238 IsUndef = false; 1239 break; 1240 } 1241 } 1242 if (IsUndef) { 1243 MO.setIsUndef(true); 1244 // We found out some subregister use is actually reading an undefined 1245 // value. In some cases the whole vreg has become undefined at this 1246 // point so we have to potentially shrink the main range if the 1247 // use was ending a live segment there. 1248 LiveQueryResult Q = Int.Query(UseIdx); 1249 if (Q.valueOut() == nullptr) 1250 ShrinkMainRange = true; 1251 } 1252} 1253 1254void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg, 1255 unsigned DstReg, 1256 unsigned SubIdx) { 1257 bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 1258 LiveInterval *DstInt = DstIsPhys ? nullptr : &LIS->getInterval(DstReg); 1259 1260 if (DstInt && DstInt->hasSubRanges() && DstReg != SrcReg) { 1261 for (MachineOperand &MO : MRI->reg_operands(DstReg)) { 1262 unsigned SubReg = MO.getSubReg(); 1263 if (SubReg == 0 || MO.isUndef()) 1264 continue; 1265 MachineInstr &MI = *MO.getParent(); 1266 if (MI.isDebugValue()) 1267 continue; 1268 SlotIndex UseIdx = LIS->getInstructionIndex(MI).getRegSlot(true); 1269 addUndefFlag(*DstInt, UseIdx, MO, SubReg); 1270 } 1271 } 1272 1273 SmallPtrSet<MachineInstr*, 8> Visited; 1274 for (MachineRegisterInfo::reg_instr_iterator 1275 I = MRI->reg_instr_begin(SrcReg), E = MRI->reg_instr_end(); 1276 I != E; ) { 1277 MachineInstr *UseMI = &*(I++); 1278 1279 // Each instruction can only be rewritten once because sub-register 1280 // composition is not always idempotent. When SrcReg != DstReg, rewriting 1281 // the UseMI operands removes them from the SrcReg use-def chain, but when 1282 // SrcReg is DstReg we could encounter UseMI twice if it has multiple 1283 // operands mentioning the virtual register. 1284 if (SrcReg == DstReg && !Visited.insert(UseMI).second) 1285 continue; 1286 1287 SmallVector<unsigned,8> Ops; 1288 bool Reads, Writes; 1289 std::tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops); 1290 1291 // If SrcReg wasn't read, it may still be the case that DstReg is live-in 1292 // because SrcReg is a sub-register. 1293 if (DstInt && !Reads && SubIdx) 1294 Reads = DstInt->liveAt(LIS->getInstructionIndex(*UseMI)); 1295 1296 // Replace SrcReg with DstReg in all UseMI operands. 1297 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 1298 MachineOperand &MO = UseMI->getOperand(Ops[i]); 1299 1300 // Adjust <undef> flags in case of sub-register joins. We don't want to 1301 // turn a full def into a read-modify-write sub-register def and vice 1302 // versa. 1303 if (SubIdx && MO.isDef()) 1304 MO.setIsUndef(!Reads); 1305 1306 // A subreg use of a partially undef (super) register may be a complete 1307 // undef use now and then has to be marked that way. 1308 if (SubIdx != 0 && MO.isUse() && MRI->shouldTrackSubRegLiveness(DstReg)) { 1309 if (!DstInt->hasSubRanges()) { 1310 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator(); 1311 LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(DstInt->reg); 1312 DstInt->createSubRangeFrom(Allocator, Mask, *DstInt); 1313 } 1314 SlotIndex MIIdx = UseMI->isDebugValue() 1315 ? LIS->getSlotIndexes()->getIndexBefore(*UseMI) 1316 : LIS->getInstructionIndex(*UseMI); 1317 SlotIndex UseIdx = MIIdx.getRegSlot(true); 1318 addUndefFlag(*DstInt, UseIdx, MO, SubIdx); 1319 } 1320 1321 if (DstIsPhys) 1322 MO.substPhysReg(DstReg, *TRI); 1323 else 1324 MO.substVirtReg(DstReg, SubIdx, *TRI); 1325 } 1326 1327 DEBUG({ 1328 dbgs() << "\t\tupdated: "; 1329 if (!UseMI->isDebugValue()) 1330 dbgs() << LIS->getInstructionIndex(*UseMI) << "\t"; 1331 dbgs() << *UseMI; 1332 }); 1333 } 1334} 1335 1336bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) { 1337 // Always join simple intervals that are defined by a single copy from a 1338 // reserved register. This doesn't increase register pressure, so it is 1339 // always beneficial. 1340 if (!MRI->isReserved(CP.getDstReg())) { 1341 DEBUG(dbgs() << "\tCan only merge into reserved registers.\n"); 1342 return false; 1343 } 1344 1345 LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg()); 1346 if (JoinVInt.containsOneValue()) 1347 return true; 1348 1349 DEBUG(dbgs() << "\tCannot join complex intervals into reserved register.\n"); 1350 return false; 1351} 1352 1353bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { 1354 1355 Again = false; 1356 DEBUG(dbgs() << LIS->getInstructionIndex(*CopyMI) << '\t' << *CopyMI); 1357 1358 CoalescerPair CP(*TRI); 1359 if (!CP.setRegisters(CopyMI)) { 1360 DEBUG(dbgs() << "\tNot coalescable.\n"); 1361 return false; 1362 } 1363 1364 if (CP.getNewRC()) { 1365 auto SrcRC = MRI->getRegClass(CP.getSrcReg()); 1366 auto DstRC = MRI->getRegClass(CP.getDstReg()); 1367 unsigned SrcIdx = CP.getSrcIdx(); 1368 unsigned DstIdx = CP.getDstIdx(); 1369 if (CP.isFlipped()) { 1370 std::swap(SrcIdx, DstIdx); 1371 std::swap(SrcRC, DstRC); 1372 } 1373 if (!TRI->shouldCoalesce(CopyMI, SrcRC, SrcIdx, DstRC, DstIdx, 1374 CP.getNewRC())) { 1375 DEBUG(dbgs() << "\tSubtarget bailed on coalescing.\n"); 1376 return false; 1377 } 1378 } 1379 1380 // Dead code elimination. This really should be handled by MachineDCE, but 1381 // sometimes dead copies slip through, and we can't generate invalid live 1382 // ranges. 1383 if (!CP.isPhys() && CopyMI->allDefsAreDead()) { 1384 DEBUG(dbgs() << "\tCopy is dead.\n"); 1385 DeadDefs.push_back(CopyMI); 1386 eliminateDeadDefs(); 1387 return true; 1388 } 1389 1390 // Eliminate undefs. 1391 if (!CP.isPhys() && eliminateUndefCopy(CopyMI)) { 1392 LIS->RemoveMachineInstrFromMaps(*CopyMI); 1393 CopyMI->eraseFromParent(); 1394 return false; // Not coalescable. 1395 } 1396 1397 // Coalesced copies are normally removed immediately, but transformations 1398 // like removeCopyByCommutingDef() can inadvertently create identity copies. 1399 // When that happens, just join the values and remove the copy. 1400 if (CP.getSrcReg() == CP.getDstReg()) { 1401 LiveInterval &LI = LIS->getInterval(CP.getSrcReg()); 1402 DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n'); 1403 const SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI); 1404 LiveQueryResult LRQ = LI.Query(CopyIdx); 1405 if (VNInfo *DefVNI = LRQ.valueDefined()) { 1406 VNInfo *ReadVNI = LRQ.valueIn(); 1407 assert(ReadVNI && "No value before copy and no <undef> flag."); 1408 assert(ReadVNI != DefVNI && "Cannot read and define the same value."); 1409 LI.MergeValueNumberInto(DefVNI, ReadVNI); 1410 1411 // Process subregister liveranges. 1412 for (LiveInterval::SubRange &S : LI.subranges()) { 1413 LiveQueryResult SLRQ = S.Query(CopyIdx); 1414 if (VNInfo *SDefVNI = SLRQ.valueDefined()) { 1415 VNInfo *SReadVNI = SLRQ.valueIn(); 1416 S.MergeValueNumberInto(SDefVNI, SReadVNI); 1417 } 1418 } 1419 DEBUG(dbgs() << "\tMerged values: " << LI << '\n'); 1420 } 1421 LIS->RemoveMachineInstrFromMaps(*CopyMI); 1422 CopyMI->eraseFromParent(); 1423 return true; 1424 } 1425 1426 // Enforce policies. 1427 if (CP.isPhys()) { 1428 DEBUG(dbgs() << "\tConsidering merging " << PrintReg(CP.getSrcReg(), TRI) 1429 << " with " << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) 1430 << '\n'); 1431 if (!canJoinPhys(CP)) { 1432 // Before giving up coalescing, if definition of source is defined by 1433 // trivial computation, try rematerializing it. 1434 bool IsDefCopy; 1435 if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy)) 1436 return true; 1437 if (IsDefCopy) 1438 Again = true; // May be possible to coalesce later. 1439 return false; 1440 } 1441 } else { 1442 // When possible, let DstReg be the larger interval. 1443 if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).size() > 1444 LIS->getInterval(CP.getDstReg()).size()) 1445 CP.flip(); 1446 1447 DEBUG({ 1448 dbgs() << "\tConsidering merging to " 1449 << TRI->getRegClassName(CP.getNewRC()) << " with "; 1450 if (CP.getDstIdx() && CP.getSrcIdx()) 1451 dbgs() << PrintReg(CP.getDstReg()) << " in " 1452 << TRI->getSubRegIndexName(CP.getDstIdx()) << " and " 1453 << PrintReg(CP.getSrcReg()) << " in " 1454 << TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n'; 1455 else 1456 dbgs() << PrintReg(CP.getSrcReg(), TRI) << " in " 1457 << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n'; 1458 }); 1459 } 1460 1461 ShrinkMask = LaneBitmask::getNone(); 1462 ShrinkMainRange = false; 1463 1464 // Okay, attempt to join these two intervals. On failure, this returns false. 1465 // Otherwise, if one of the intervals being joined is a physreg, this method 1466 // always canonicalizes DstInt to be it. The output "SrcInt" will not have 1467 // been modified, so we can use this information below to update aliases. 1468 if (!joinIntervals(CP)) { 1469 // Coalescing failed. 1470 1471 // If definition of source is defined by trivial computation, try 1472 // rematerializing it. 1473 bool IsDefCopy; 1474 if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy)) 1475 return true; 1476 1477 // If we can eliminate the copy without merging the live segments, do so 1478 // now. 1479 if (!CP.isPartial() && !CP.isPhys()) { 1480 if (adjustCopiesBackFrom(CP, CopyMI) || 1481 removeCopyByCommutingDef(CP, CopyMI)) { 1482 LIS->RemoveMachineInstrFromMaps(*CopyMI); 1483 CopyMI->eraseFromParent(); 1484 DEBUG(dbgs() << "\tTrivial!\n"); 1485 return true; 1486 } 1487 } 1488 1489 // Otherwise, we are unable to join the intervals. 1490 DEBUG(dbgs() << "\tInterference!\n"); 1491 Again = true; // May be possible to coalesce later. 1492 return false; 1493 } 1494 1495 // Coalescing to a virtual register that is of a sub-register class of the 1496 // other. Make sure the resulting register is set to the right register class. 1497 if (CP.isCrossClass()) { 1498 ++numCrossRCs; 1499 MRI->setRegClass(CP.getDstReg(), CP.getNewRC()); 1500 } 1501 1502 // Removing sub-register copies can ease the register class constraints. 1503 // Make sure we attempt to inflate the register class of DstReg. 1504 if (!CP.isPhys() && RegClassInfo.isProperSubClass(CP.getNewRC())) 1505 InflateRegs.push_back(CP.getDstReg()); 1506 1507 // CopyMI has been erased by joinIntervals at this point. Remove it from 1508 // ErasedInstrs since copyCoalesceWorkList() won't add a successful join back 1509 // to the work list. This keeps ErasedInstrs from growing needlessly. 1510 ErasedInstrs.erase(CopyMI); 1511 1512 // Rewrite all SrcReg operands to DstReg. 1513 // Also update DstReg operands to include DstIdx if it is set. 1514 if (CP.getDstIdx()) 1515 updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx()); 1516 updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx()); 1517 1518 // Shrink subregister ranges if necessary. 1519 if (ShrinkMask.any()) { 1520 LiveInterval &LI = LIS->getInterval(CP.getDstReg()); 1521 for (LiveInterval::SubRange &S : LI.subranges()) { 1522 if ((S.LaneMask & ShrinkMask).none()) 1523 continue; 1524 DEBUG(dbgs() << "Shrink LaneUses (Lane " << PrintLaneMask(S.LaneMask) 1525 << ")\n"); 1526 LIS->shrinkToUses(S, LI.reg); 1527 } 1528 LI.removeEmptySubRanges(); 1529 } 1530 if (ShrinkMainRange) { 1531 LiveInterval &LI = LIS->getInterval(CP.getDstReg()); 1532 shrinkToUses(&LI); 1533 } 1534 1535 // SrcReg is guaranteed to be the register whose live interval that is 1536 // being merged. 1537 LIS->removeInterval(CP.getSrcReg()); 1538 1539 // Update regalloc hint. 1540 TRI->updateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF); 1541 1542 DEBUG({ 1543 dbgs() << "\tSuccess: " << PrintReg(CP.getSrcReg(), TRI, CP.getSrcIdx()) 1544 << " -> " << PrintReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n'; 1545 dbgs() << "\tResult = "; 1546 if (CP.isPhys()) 1547 dbgs() << PrintReg(CP.getDstReg(), TRI); 1548 else 1549 dbgs() << LIS->getInterval(CP.getDstReg()); 1550 dbgs() << '\n'; 1551 }); 1552 1553 ++numJoins; 1554 return true; 1555} 1556 1557bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) { 1558 unsigned DstReg = CP.getDstReg(); 1559 unsigned SrcReg = CP.getSrcReg(); 1560 assert(CP.isPhys() && "Must be a physreg copy"); 1561 assert(MRI->isReserved(DstReg) && "Not a reserved register"); 1562 LiveInterval &RHS = LIS->getInterval(SrcReg); 1563 DEBUG(dbgs() << "\t\tRHS = " << RHS << '\n'); 1564 1565 assert(RHS.containsOneValue() && "Invalid join with reserved register"); 1566 1567 // Optimization for reserved registers like ESP. We can only merge with a 1568 // reserved physreg if RHS has a single value that is a copy of DstReg. 1569 // The live range of the reserved register will look like a set of dead defs 1570 // - we don't properly track the live range of reserved registers. 1571 1572 // Deny any overlapping intervals. This depends on all the reserved 1573 // register live ranges to look like dead defs. 1574 if (!MRI->isConstantPhysReg(DstReg)) { 1575 for (MCRegUnitIterator UI(DstReg, TRI); UI.isValid(); ++UI) { 1576 // Abort if not all the regunits are reserved. 1577 for (MCRegUnitRootIterator RI(*UI, TRI); RI.isValid(); ++RI) { 1578 if (!MRI->isReserved(*RI)) 1579 return false; 1580 } 1581 if (RHS.overlaps(LIS->getRegUnit(*UI))) { 1582 DEBUG(dbgs() << "\t\tInterference: " << PrintRegUnit(*UI, TRI) << '\n'); 1583 return false; 1584 } 1585 } 1586 } 1587 1588 // Skip any value computations, we are not adding new values to the 1589 // reserved register. Also skip merging the live ranges, the reserved 1590 // register live range doesn't need to be accurate as long as all the 1591 // defs are there. 1592 1593 // Delete the identity copy. 1594 MachineInstr *CopyMI; 1595 if (CP.isFlipped()) { 1596 // Physreg is copied into vreg 1597 // %vregY = COPY %X 1598 // ... //< no other def of %X here 1599 // use %vregY 1600 // => 1601 // ... 1602 // use %X 1603 CopyMI = MRI->getVRegDef(SrcReg); 1604 } else { 1605 // VReg is copied into physreg: 1606 // %vregX = def 1607 // ... //< no other def or use of %Y here 1608 // %Y = COPY %vregX 1609 // => 1610 // %Y = def 1611 // ... 1612 if (!MRI->hasOneNonDBGUse(SrcReg)) { 1613 DEBUG(dbgs() << "\t\tMultiple vreg uses!\n"); 1614 return false; 1615 } 1616 1617 if (!LIS->intervalIsInOneMBB(RHS)) { 1618 DEBUG(dbgs() << "\t\tComplex control flow!\n"); 1619 return false; 1620 } 1621 1622 MachineInstr &DestMI = *MRI->getVRegDef(SrcReg); 1623 CopyMI = &*MRI->use_instr_nodbg_begin(SrcReg); 1624 SlotIndex CopyRegIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot(); 1625 SlotIndex DestRegIdx = LIS->getInstructionIndex(DestMI).getRegSlot(); 1626 1627 if (!MRI->isConstantPhysReg(DstReg)) { 1628 // We checked above that there are no interfering defs of the physical 1629 // register. However, for this case, where we intent to move up the def of 1630 // the physical register, we also need to check for interfering uses. 1631 SlotIndexes *Indexes = LIS->getSlotIndexes(); 1632 for (SlotIndex SI = Indexes->getNextNonNullIndex(DestRegIdx); 1633 SI != CopyRegIdx; SI = Indexes->getNextNonNullIndex(SI)) { 1634 MachineInstr *MI = LIS->getInstructionFromIndex(SI); 1635 if (MI->readsRegister(DstReg, TRI)) { 1636 DEBUG(dbgs() << "\t\tInterference (read): " << *MI); 1637 return false; 1638 } 1639 1640 // We must also check for clobbers caused by regmasks. 1641 for (const auto &MO : MI->operands()) { 1642 if (MO.isRegMask() && MO.clobbersPhysReg(DstReg)) { 1643 DEBUG(dbgs() << "\t\tInterference (regmask clobber): " << *MI); 1644 return false; 1645 } 1646 } 1647 } 1648 } 1649 1650 // We're going to remove the copy which defines a physical reserved 1651 // register, so remove its valno, etc. 1652 DEBUG(dbgs() << "\t\tRemoving phys reg def of " << PrintReg(DstReg, TRI) 1653 << " at " << CopyRegIdx << "\n"); 1654 1655 LIS->removePhysRegDefAt(DstReg, CopyRegIdx); 1656 // Create a new dead def at the new def location. 1657 for (MCRegUnitIterator UI(DstReg, TRI); UI.isValid(); ++UI) { 1658 LiveRange &LR = LIS->getRegUnit(*UI); 1659 LR.createDeadDef(DestRegIdx, LIS->getVNInfoAllocator()); 1660 } 1661 } 1662 1663 LIS->RemoveMachineInstrFromMaps(*CopyMI); 1664 CopyMI->eraseFromParent(); 1665 1666 // We don't track kills for reserved registers. 1667 MRI->clearKillFlags(CP.getSrcReg()); 1668 1669 return true; 1670} 1671 1672//===----------------------------------------------------------------------===// 1673// Interference checking and interval joining 1674//===----------------------------------------------------------------------===// 1675// 1676// In the easiest case, the two live ranges being joined are disjoint, and 1677// there is no interference to consider. It is quite common, though, to have 1678// overlapping live ranges, and we need to check if the interference can be 1679// resolved. 1680// 1681// The live range of a single SSA value forms a sub-tree of the dominator tree. 1682// This means that two SSA values overlap if and only if the def of one value 1683// is contained in the live range of the other value. As a special case, the 1684// overlapping values can be defined at the same index. 1685// 1686// The interference from an overlapping def can be resolved in these cases: 1687// 1688// 1. Coalescable copies. The value is defined by a copy that would become an 1689// identity copy after joining SrcReg and DstReg. The copy instruction will 1690// be removed, and the value will be merged with the source value. 1691// 1692// There can be several copies back and forth, causing many values to be 1693// merged into one. We compute a list of ultimate values in the joined live 1694// range as well as a mappings from the old value numbers. 1695// 1696// 2. IMPLICIT_DEF. This instruction is only inserted to ensure all PHI 1697// predecessors have a live out value. It doesn't cause real interference, 1698// and can be merged into the value it overlaps. Like a coalescable copy, it 1699// can be erased after joining. 1700// 1701// 3. Copy of external value. The overlapping def may be a copy of a value that 1702// is already in the other register. This is like a coalescable copy, but 1703// the live range of the source register must be trimmed after erasing the 1704// copy instruction: 1705// 1706// %src = COPY %ext 1707// %dst = COPY %ext <-- Remove this COPY, trim the live range of %ext. 1708// 1709// 4. Clobbering undefined lanes. Vector registers are sometimes built by 1710// defining one lane at a time: 1711// 1712// %dst:ssub0<def,read-undef> = FOO 1713// %src = BAR 1714// %dst:ssub1<def> = COPY %src 1715// 1716// The live range of %src overlaps the %dst value defined by FOO, but 1717// merging %src into %dst:ssub1 is only going to clobber the ssub1 lane 1718// which was undef anyway. 1719// 1720// The value mapping is more complicated in this case. The final live range 1721// will have different value numbers for both FOO and BAR, but there is no 1722// simple mapping from old to new values. It may even be necessary to add 1723// new PHI values. 1724// 1725// 5. Clobbering dead lanes. A def may clobber a lane of a vector register that 1726// is live, but never read. This can happen because we don't compute 1727// individual live ranges per lane. 1728// 1729// %dst<def> = FOO 1730// %src = BAR 1731// %dst:ssub1<def> = COPY %src 1732// 1733// This kind of interference is only resolved locally. If the clobbered 1734// lane value escapes the block, the join is aborted. 1735 1736namespace { 1737/// Track information about values in a single virtual register about to be 1738/// joined. Objects of this class are always created in pairs - one for each 1739/// side of the CoalescerPair (or one for each lane of a side of the coalescer 1740/// pair) 1741class JoinVals { 1742 /// Live range we work on. 1743 LiveRange &LR; 1744 /// (Main) register we work on. 1745 const unsigned Reg; 1746 1747 /// Reg (and therefore the values in this liverange) will end up as 1748 /// subregister SubIdx in the coalesced register. Either CP.DstIdx or 1749 /// CP.SrcIdx. 1750 const unsigned SubIdx; 1751 /// The LaneMask that this liverange will occupy the coalesced register. May 1752 /// be smaller than the lanemask produced by SubIdx when merging subranges. 1753 const LaneBitmask LaneMask; 1754 1755 /// This is true when joining sub register ranges, false when joining main 1756 /// ranges. 1757 const bool SubRangeJoin; 1758 /// Whether the current LiveInterval tracks subregister liveness. 1759 const bool TrackSubRegLiveness; 1760 1761 /// Values that will be present in the final live range. 1762 SmallVectorImpl<VNInfo*> &NewVNInfo; 1763 1764 const CoalescerPair &CP; 1765 LiveIntervals *LIS; 1766 SlotIndexes *Indexes; 1767 const TargetRegisterInfo *TRI; 1768 1769 /// Value number assignments. Maps value numbers in LI to entries in 1770 /// NewVNInfo. This is suitable for passing to LiveInterval::join(). 1771 SmallVector<int, 8> Assignments; 1772 1773 /// Conflict resolution for overlapping values. 1774 enum ConflictResolution { 1775 /// No overlap, simply keep this value. 1776 CR_Keep, 1777 1778 /// Merge this value into OtherVNI and erase the defining instruction. 1779 /// Used for IMPLICIT_DEF, coalescable copies, and copies from external 1780 /// values. 1781 CR_Erase, 1782 1783 /// Merge this value into OtherVNI but keep the defining instruction. 1784 /// This is for the special case where OtherVNI is defined by the same 1785 /// instruction. 1786 CR_Merge, 1787 1788 /// Keep this value, and have it replace OtherVNI where possible. This 1789 /// complicates value mapping since OtherVNI maps to two different values 1790 /// before and after this def. 1791 /// Used when clobbering undefined or dead lanes. 1792 CR_Replace, 1793 1794 /// Unresolved conflict. Visit later when all values have been mapped. 1795 CR_Unresolved, 1796 1797 /// Unresolvable conflict. Abort the join. 1798 CR_Impossible 1799 }; 1800 1801 /// Per-value info for LI. The lane bit masks are all relative to the final 1802 /// joined register, so they can be compared directly between SrcReg and 1803 /// DstReg. 1804 struct Val { 1805 ConflictResolution Resolution; 1806 1807 /// Lanes written by this def, 0 for unanalyzed values. 1808 LaneBitmask WriteLanes; 1809 1810 /// Lanes with defined values in this register. Other lanes are undef and 1811 /// safe to clobber. 1812 LaneBitmask ValidLanes; 1813 1814 /// Value in LI being redefined by this def. 1815 VNInfo *RedefVNI; 1816 1817 /// Value in the other live range that overlaps this def, if any. 1818 VNInfo *OtherVNI; 1819 1820 /// Is this value an IMPLICIT_DEF that can be erased? 1821 /// 1822 /// IMPLICIT_DEF values should only exist at the end of a basic block that 1823 /// is a predecessor to a phi-value. These IMPLICIT_DEF instructions can be 1824 /// safely erased if they are overlapping a live value in the other live 1825 /// interval. 1826 /// 1827 /// Weird control flow graphs and incomplete PHI handling in 1828 /// ProcessImplicitDefs can very rarely create IMPLICIT_DEF values with 1829 /// longer live ranges. Such IMPLICIT_DEF values should be treated like 1830 /// normal values. 1831 bool ErasableImplicitDef; 1832 1833 /// True when the live range of this value will be pruned because of an 1834 /// overlapping CR_Replace value in the other live range. 1835 bool Pruned; 1836 1837 /// True once Pruned above has been computed. 1838 bool PrunedComputed; 1839 1840 Val() : Resolution(CR_Keep), WriteLanes(), ValidLanes(), 1841 RedefVNI(nullptr), OtherVNI(nullptr), ErasableImplicitDef(false), 1842 Pruned(false), PrunedComputed(false) {} 1843 1844 bool isAnalyzed() const { return WriteLanes.any(); } 1845 }; 1846 1847 /// One entry per value number in LI. 1848 SmallVector<Val, 8> Vals; 1849 1850 /// Compute the bitmask of lanes actually written by DefMI. 1851 /// Set Redef if there are any partial register definitions that depend on the 1852 /// previous value of the register. 1853 LaneBitmask computeWriteLanes(const MachineInstr *DefMI, bool &Redef) const; 1854 1855 /// Find the ultimate value that VNI was copied from. 1856 std::pair<const VNInfo*,unsigned> followCopyChain(const VNInfo *VNI) const; 1857 1858 bool valuesIdentical(VNInfo *Val0, VNInfo *Val1, const JoinVals &Other) const; 1859 1860 /// Analyze ValNo in this live range, and set all fields of Vals[ValNo]. 1861 /// Return a conflict resolution when possible, but leave the hard cases as 1862 /// CR_Unresolved. 1863 /// Recursively calls computeAssignment() on this and Other, guaranteeing that 1864 /// both OtherVNI and RedefVNI have been analyzed and mapped before returning. 1865 /// The recursion always goes upwards in the dominator tree, making loops 1866 /// impossible. 1867 ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other); 1868 1869 /// Compute the value assignment for ValNo in RI. 1870 /// This may be called recursively by analyzeValue(), but never for a ValNo on 1871 /// the stack. 1872 void computeAssignment(unsigned ValNo, JoinVals &Other); 1873 1874 /// Assuming ValNo is going to clobber some valid lanes in Other.LR, compute 1875 /// the extent of the tainted lanes in the block. 1876 /// 1877 /// Multiple values in Other.LR can be affected since partial redefinitions 1878 /// can preserve previously tainted lanes. 1879 /// 1880 /// 1 %dst = VLOAD <-- Define all lanes in %dst 1881 /// 2 %src = FOO <-- ValNo to be joined with %dst:ssub0 1882 /// 3 %dst:ssub1 = BAR <-- Partial redef doesn't clear taint in ssub0 1883 /// 4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read 1884 /// 1885 /// For each ValNo in Other that is affected, add an (EndIndex, TaintedLanes) 1886 /// entry to TaintedVals. 1887 /// 1888 /// Returns false if the tainted lanes extend beyond the basic block. 1889 bool taintExtent(unsigned, LaneBitmask, JoinVals&, 1890 SmallVectorImpl<std::pair<SlotIndex, LaneBitmask> >&); 1891 1892 /// Return true if MI uses any of the given Lanes from Reg. 1893 /// This does not include partial redefinitions of Reg. 1894 bool usesLanes(const MachineInstr &MI, unsigned, unsigned, LaneBitmask) const; 1895 1896 /// Determine if ValNo is a copy of a value number in LR or Other.LR that will 1897 /// be pruned: 1898 /// 1899 /// %dst = COPY %src 1900 /// %src = COPY %dst <-- This value to be pruned. 1901 /// %dst = COPY %src <-- This value is a copy of a pruned value. 1902 bool isPrunedValue(unsigned ValNo, JoinVals &Other); 1903 1904public: 1905 JoinVals(LiveRange &LR, unsigned Reg, unsigned SubIdx, LaneBitmask LaneMask, 1906 SmallVectorImpl<VNInfo*> &newVNInfo, const CoalescerPair &cp, 1907 LiveIntervals *lis, const TargetRegisterInfo *TRI, bool SubRangeJoin, 1908 bool TrackSubRegLiveness) 1909 : LR(LR), Reg(Reg), SubIdx(SubIdx), LaneMask(LaneMask), 1910 SubRangeJoin(SubRangeJoin), TrackSubRegLiveness(TrackSubRegLiveness), 1911 NewVNInfo(newVNInfo), CP(cp), LIS(lis), Indexes(LIS->getSlotIndexes()), 1912 TRI(TRI), Assignments(LR.getNumValNums(), -1), Vals(LR.getNumValNums()) 1913 {} 1914 1915 /// Analyze defs in LR and compute a value mapping in NewVNInfo. 1916 /// Returns false if any conflicts were impossible to resolve. 1917 bool mapValues(JoinVals &Other); 1918 1919 /// Try to resolve conflicts that require all values to be mapped. 1920 /// Returns false if any conflicts were impossible to resolve. 1921 bool resolveConflicts(JoinVals &Other); 1922 1923 /// Prune the live range of values in Other.LR where they would conflict with 1924 /// CR_Replace values in LR. Collect end points for restoring the live range 1925 /// after joining. 1926 void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints, 1927 bool changeInstrs); 1928 1929 /// Removes subranges starting at copies that get removed. This sometimes 1930 /// happens when undefined subranges are copied around. These ranges contain 1931 /// no useful information and can be removed. 1932 void pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask); 1933 1934 /// Pruning values in subranges can lead to removing segments in these 1935 /// subranges started by IMPLICIT_DEFs. The corresponding segments in 1936 /// the main range also need to be removed. This function will mark 1937 /// the corresponding values in the main range as pruned, so that 1938 /// eraseInstrs can do the final cleanup. 1939 /// The parameter @p LI must be the interval whose main range is the 1940 /// live range LR. 1941 void pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange); 1942 1943 /// Erase any machine instructions that have been coalesced away. 1944 /// Add erased instructions to ErasedInstrs. 1945 /// Add foreign virtual registers to ShrinkRegs if their live range ended at 1946 /// the erased instrs. 1947 void eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs, 1948 SmallVectorImpl<unsigned> &ShrinkRegs, 1949 LiveInterval *LI = nullptr); 1950 1951 /// Remove liverange defs at places where implicit defs will be removed. 1952 void removeImplicitDefs(); 1953 1954 /// Get the value assignments suitable for passing to LiveInterval::join. 1955 const int *getAssignments() const { return Assignments.data(); } 1956}; 1957} // end anonymous namespace 1958 1959LaneBitmask JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef) 1960 const { 1961 LaneBitmask L; 1962 for (const MachineOperand &MO : DefMI->operands()) { 1963 if (!MO.isReg() || MO.getReg() != Reg || !MO.isDef()) 1964 continue; 1965 L |= TRI->getSubRegIndexLaneMask( 1966 TRI->composeSubRegIndices(SubIdx, MO.getSubReg())); 1967 if (MO.readsReg()) 1968 Redef = true; 1969 } 1970 return L; 1971} 1972 1973std::pair<const VNInfo*, unsigned> JoinVals::followCopyChain( 1974 const VNInfo *VNI) const { 1975 unsigned Reg = this->Reg; 1976 1977 while (!VNI->isPHIDef()) { 1978 SlotIndex Def = VNI->def; 1979 MachineInstr *MI = Indexes->getInstructionFromIndex(Def); 1980 assert(MI && "No defining instruction"); 1981 if (!MI->isFullCopy()) 1982 return std::make_pair(VNI, Reg); 1983 unsigned SrcReg = MI->getOperand(1).getReg(); 1984 if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) 1985 return std::make_pair(VNI, Reg); 1986 1987 const LiveInterval &LI = LIS->getInterval(SrcReg); 1988 const VNInfo *ValueIn; 1989 // No subrange involved. 1990 if (!SubRangeJoin || !LI.hasSubRanges()) { 1991 LiveQueryResult LRQ = LI.Query(Def); 1992 ValueIn = LRQ.valueIn(); 1993 } else { 1994 // Query subranges. Pick the first matching one. 1995 ValueIn = nullptr; 1996 for (const LiveInterval::SubRange &S : LI.subranges()) { 1997 // Transform lanemask to a mask in the joined live interval. 1998 LaneBitmask SMask = TRI->composeSubRegIndexLaneMask(SubIdx, S.LaneMask); 1999 if ((SMask & LaneMask).none()) 2000 continue; 2001 LiveQueryResult LRQ = S.Query(Def); 2002 ValueIn = LRQ.valueIn(); 2003 break; 2004 } 2005 } 2006 if (ValueIn == nullptr) 2007 break; 2008 VNI = ValueIn; 2009 Reg = SrcReg; 2010 } 2011 return std::make_pair(VNI, Reg); 2012} 2013 2014bool JoinVals::valuesIdentical(VNInfo *Value0, VNInfo *Value1, 2015 const JoinVals &Other) const { 2016 const VNInfo *Orig0; 2017 unsigned Reg0; 2018 std::tie(Orig0, Reg0) = followCopyChain(Value0); 2019 if (Orig0 == Value1) 2020 return true; 2021 2022 const VNInfo *Orig1; 2023 unsigned Reg1; 2024 std::tie(Orig1, Reg1) = Other.followCopyChain(Value1); 2025 2026 // The values are equal if they are defined at the same place and use the 2027 // same register. Note that we cannot compare VNInfos directly as some of 2028 // them might be from a copy created in mergeSubRangeInto() while the other 2029 // is from the original LiveInterval. 2030 return Orig0->def == Orig1->def && Reg0 == Reg1; 2031} 2032 2033JoinVals::ConflictResolution 2034JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) { 2035 Val &V = Vals[ValNo]; 2036 assert(!V.isAnalyzed() && "Value has already been analyzed!"); 2037 VNInfo *VNI = LR.getValNumInfo(ValNo); 2038 if (VNI->isUnused()) { 2039 V.WriteLanes = LaneBitmask::getAll(); 2040 return CR_Keep; 2041 } 2042 2043 // Get the instruction defining this value, compute the lanes written. 2044 const MachineInstr *DefMI = nullptr; 2045 if (VNI->isPHIDef()) { 2046 // Conservatively assume that all lanes in a PHI are valid. 2047 LaneBitmask Lanes = SubRangeJoin ? LaneBitmask(1) 2048 : TRI->getSubRegIndexLaneMask(SubIdx); 2049 V.ValidLanes = V.WriteLanes = Lanes; 2050 } else { 2051 DefMI = Indexes->getInstructionFromIndex(VNI->def); 2052 assert(DefMI != nullptr); 2053 if (SubRangeJoin) { 2054 // We don't care about the lanes when joining subregister ranges. 2055 V.WriteLanes = V.ValidLanes = LaneBitmask(1); 2056 if (DefMI->isImplicitDef()) { 2057 V.ValidLanes = LaneBitmask::getNone(); 2058 V.ErasableImplicitDef = true; 2059 } 2060 } else { 2061 bool Redef = false; 2062 V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef); 2063 2064 // If this is a read-modify-write instruction, there may be more valid 2065 // lanes than the ones written by this instruction. 2066 // This only covers partial redef operands. DefMI may have normal use 2067 // operands reading the register. They don't contribute valid lanes. 2068 // 2069 // This adds ssub1 to the set of valid lanes in %src: 2070 // 2071 // %src:ssub1<def> = FOO 2072 // 2073 // This leaves only ssub1 valid, making any other lanes undef: 2074 // 2075 // %src:ssub1<def,read-undef> = FOO %src:ssub2 2076 // 2077 // The <read-undef> flag on the def operand means that old lane values are 2078 // not important. 2079 if (Redef) { 2080 V.RedefVNI = LR.Query(VNI->def).valueIn(); 2081 assert((TrackSubRegLiveness || V.RedefVNI) && 2082 "Instruction is reading nonexistent value"); 2083 if (V.RedefVNI != nullptr) { 2084 computeAssignment(V.RedefVNI->id, Other); 2085 V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes; 2086 } 2087 } 2088 2089 // An IMPLICIT_DEF writes undef values. 2090 if (DefMI->isImplicitDef()) { 2091 // We normally expect IMPLICIT_DEF values to be live only until the end 2092 // of their block. If the value is really live longer and gets pruned in 2093 // another block, this flag is cleared again. 2094 V.ErasableImplicitDef = true; 2095 V.ValidLanes &= ~V.WriteLanes; 2096 } 2097 } 2098 } 2099 2100 // Find the value in Other that overlaps VNI->def, if any. 2101 LiveQueryResult OtherLRQ = Other.LR.Query(VNI->def); 2102 2103 // It is possible that both values are defined by the same instruction, or 2104 // the values are PHIs defined in the same block. When that happens, the two 2105 // values should be merged into one, but not into any preceding value. 2106 // The first value defined or visited gets CR_Keep, the other gets CR_Merge. 2107 if (VNInfo *OtherVNI = OtherLRQ.valueDefined()) { 2108 assert(SlotIndex::isSameInstr(VNI->def, OtherVNI->def) && "Broken LRQ"); 2109 2110 // One value stays, the other is merged. Keep the earlier one, or the first 2111 // one we see. 2112 if (OtherVNI->def < VNI->def) 2113 Other.computeAssignment(OtherVNI->id, *this); 2114 else if (VNI->def < OtherVNI->def && OtherLRQ.valueIn()) { 2115 // This is an early-clobber def overlapping a live-in value in the other 2116 // register. Not mergeable. 2117 V.OtherVNI = OtherLRQ.valueIn(); 2118 return CR_Impossible; 2119 } 2120 V.OtherVNI = OtherVNI; 2121 Val &OtherV = Other.Vals[OtherVNI->id]; 2122 // Keep this value, check for conflicts when analyzing OtherVNI. 2123 if (!OtherV.isAnalyzed()) 2124 return CR_Keep; 2125 // Both sides have been analyzed now. 2126 // Allow overlapping PHI values. Any real interference would show up in a 2127 // predecessor, the PHI itself can't introduce any conflicts. 2128 if (VNI->isPHIDef()) 2129 return CR_Merge; 2130 if ((V.ValidLanes & OtherV.ValidLanes).any()) 2131 // Overlapping lanes can't be resolved. 2132 return CR_Impossible; 2133 else 2134 return CR_Merge; 2135 } 2136 2137 // No simultaneous def. Is Other live at the def? 2138 V.OtherVNI = OtherLRQ.valueIn(); 2139 if (!V.OtherVNI) 2140 // No overlap, no conflict. 2141 return CR_Keep; 2142 2143 assert(!SlotIndex::isSameInstr(VNI->def, V.OtherVNI->def) && "Broken LRQ"); 2144 2145 // We have overlapping values, or possibly a kill of Other. 2146 // Recursively compute assignments up the dominator tree. 2147 Other.computeAssignment(V.OtherVNI->id, *this); 2148 Val &OtherV = Other.Vals[V.OtherVNI->id]; 2149 2150 // Check if OtherV is an IMPLICIT_DEF that extends beyond its basic block. 2151 // This shouldn't normally happen, but ProcessImplicitDefs can leave such 2152 // IMPLICIT_DEF instructions behind, and there is nothing wrong with it 2153 // technically. 2154 // 2155 // When it happens, treat that IMPLICIT_DEF as a normal value, and don't try 2156 // to erase the IMPLICIT_DEF instruction. 2157 if (OtherV.ErasableImplicitDef && DefMI && 2158 DefMI->getParent() != Indexes->getMBBFromIndex(V.OtherVNI->def)) { 2159 DEBUG(dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def 2160 << " extends into BB#" << DefMI->getParent()->getNumber() 2161 << ", keeping it.\n"); 2162 OtherV.ErasableImplicitDef = false; 2163 } 2164 2165 // Allow overlapping PHI values. Any real interference would show up in a 2166 // predecessor, the PHI itself can't introduce any conflicts. 2167 if (VNI->isPHIDef()) 2168 return CR_Replace; 2169 2170 // Check for simple erasable conflicts. 2171 if (DefMI->isImplicitDef()) { 2172 // We need the def for the subregister if there is nothing else live at the 2173 // subrange at this point. 2174 if (TrackSubRegLiveness 2175 && (V.WriteLanes & (OtherV.ValidLanes | OtherV.WriteLanes)).none()) 2176 return CR_Replace; 2177 return CR_Erase; 2178 } 2179 2180 // Include the non-conflict where DefMI is a coalescable copy that kills 2181 // OtherVNI. We still want the copy erased and value numbers merged. 2182 if (CP.isCoalescable(DefMI)) { 2183 // Some of the lanes copied from OtherVNI may be undef, making them undef 2184 // here too. 2185 V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes; 2186 return CR_Erase; 2187 } 2188 2189 // This may not be a real conflict if DefMI simply kills Other and defines 2190 // VNI. 2191 if (OtherLRQ.isKill() && OtherLRQ.endPoint() <= VNI->def) 2192 return CR_Keep; 2193 2194 // Handle the case where VNI and OtherVNI can be proven to be identical: 2195 // 2196 // %other = COPY %ext 2197 // %this = COPY %ext <-- Erase this copy 2198 // 2199 if (DefMI->isFullCopy() && !CP.isPartial() 2200 && valuesIdentical(VNI, V.OtherVNI, Other)) 2201 return CR_Erase; 2202 2203 // If the lanes written by this instruction were all undef in OtherVNI, it is 2204 // still safe to join the live ranges. This can't be done with a simple value 2205 // mapping, though - OtherVNI will map to multiple values: 2206 // 2207 // 1 %dst:ssub0 = FOO <-- OtherVNI 2208 // 2 %src = BAR <-- VNI 2209 // 3 %dst:ssub1 = COPY %src<kill> <-- Eliminate this copy. 2210 // 4 BAZ %dst<kill> 2211 // 5 QUUX %src<kill> 2212 // 2213 // Here OtherVNI will map to itself in [1;2), but to VNI in [2;5). CR_Replace 2214 // handles this complex value mapping. 2215 if ((V.WriteLanes & OtherV.ValidLanes).none()) 2216 return CR_Replace; 2217 2218 // If the other live range is killed by DefMI and the live ranges are still 2219 // overlapping, it must be because we're looking at an early clobber def: 2220 // 2221 // %dst<def,early-clobber> = ASM %src<kill> 2222 // 2223 // In this case, it is illegal to merge the two live ranges since the early 2224 // clobber def would clobber %src before it was read. 2225 if (OtherLRQ.isKill()) { 2226 // This case where the def doesn't overlap the kill is handled above. 2227 assert(VNI->def.isEarlyClobber() && 2228 "Only early clobber defs can overlap a kill"); 2229 return CR_Impossible; 2230 } 2231 2232 // VNI is clobbering live lanes in OtherVNI, but there is still the 2233 // possibility that no instructions actually read the clobbered lanes. 2234 // If we're clobbering all the lanes in OtherVNI, at least one must be read. 2235 // Otherwise Other.RI wouldn't be live here. 2236 if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes).none()) 2237 return CR_Impossible; 2238 2239 // We need to verify that no instructions are reading the clobbered lanes. To 2240 // save compile time, we'll only check that locally. Don't allow the tainted 2241 // value to escape the basic block. 2242 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 2243 if (OtherLRQ.endPoint() >= Indexes->getMBBEndIdx(MBB)) 2244 return CR_Impossible; 2245 2246 // There are still some things that could go wrong besides clobbered lanes 2247 // being read, for example OtherVNI may be only partially redefined in MBB, 2248 // and some clobbered lanes could escape the block. Save this analysis for 2249 // resolveConflicts() when all values have been mapped. We need to know 2250 // RedefVNI and WriteLanes for any later defs in MBB, and we can't compute 2251 // that now - the recursive analyzeValue() calls must go upwards in the 2252 // dominator tree. 2253 return CR_Unresolved; 2254} 2255 2256void JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) { 2257 Val &V = Vals[ValNo]; 2258 if (V.isAnalyzed()) { 2259 // Recursion should always move up the dominator tree, so ValNo is not 2260 // supposed to reappear before it has been assigned. 2261 assert(Assignments[ValNo] != -1 && "Bad recursion?"); 2262 return; 2263 } 2264 switch ((V.Resolution = analyzeValue(ValNo, Other))) { 2265 case CR_Erase: 2266 case CR_Merge: 2267 // Merge this ValNo into OtherVNI. 2268 assert(V.OtherVNI && "OtherVNI not assigned, can't merge."); 2269 assert(Other.Vals[V.OtherVNI->id].isAnalyzed() && "Missing recursion"); 2270 Assignments[ValNo] = Other.Assignments[V.OtherVNI->id]; 2271 DEBUG(dbgs() << "\t\tmerge " << PrintReg(Reg) << ':' << ValNo << '@' 2272 << LR.getValNumInfo(ValNo)->def << " into " 2273 << PrintReg(Other.Reg) << ':' << V.OtherVNI->id << '@' 2274 << V.OtherVNI->def << " --> @" 2275 << NewVNInfo[Assignments[ValNo]]->def << '\n'); 2276 break; 2277 case CR_Replace: 2278 case CR_Unresolved: { 2279 // The other value is going to be pruned if this join is successful. 2280 assert(V.OtherVNI && "OtherVNI not assigned, can't prune"); 2281 Val &OtherV = Other.Vals[V.OtherVNI->id]; 2282 // We cannot erase an IMPLICIT_DEF if we don't have valid values for all 2283 // its lanes. 2284 if ((OtherV.WriteLanes & ~V.ValidLanes).any() && TrackSubRegLiveness) 2285 OtherV.ErasableImplicitDef = false; 2286 OtherV.Pruned = true; 2287 LLVM_FALLTHROUGH; 2288 } 2289 default: 2290 // This value number needs to go in the final joined live range. 2291 Assignments[ValNo] = NewVNInfo.size(); 2292 NewVNInfo.push_back(LR.getValNumInfo(ValNo)); 2293 break; 2294 } 2295} 2296 2297bool JoinVals::mapValues(JoinVals &Other) { 2298 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) { 2299 computeAssignment(i, Other); 2300 if (Vals[i].Resolution == CR_Impossible) { 2301 DEBUG(dbgs() << "\t\tinterference at " << PrintReg(Reg) << ':' << i 2302 << '@' << LR.getValNumInfo(i)->def << '\n'); 2303 return false; 2304 } 2305 } 2306 return true; 2307} 2308 2309bool JoinVals:: 2310taintExtent(unsigned ValNo, LaneBitmask TaintedLanes, JoinVals &Other, 2311 SmallVectorImpl<std::pair<SlotIndex, LaneBitmask> > &TaintExtent) { 2312 VNInfo *VNI = LR.getValNumInfo(ValNo); 2313 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 2314 SlotIndex MBBEnd = Indexes->getMBBEndIdx(MBB); 2315 2316 // Scan Other.LR from VNI.def to MBBEnd. 2317 LiveInterval::iterator OtherI = Other.LR.find(VNI->def); 2318 assert(OtherI != Other.LR.end() && "No conflict?"); 2319 do { 2320 // OtherI is pointing to a tainted value. Abort the join if the tainted 2321 // lanes escape the block. 2322 SlotIndex End = OtherI->end; 2323 if (End >= MBBEnd) { 2324 DEBUG(dbgs() << "\t\ttaints global " << PrintReg(Other.Reg) << ':' 2325 << OtherI->valno->id << '@' << OtherI->start << '\n'); 2326 return false; 2327 } 2328 DEBUG(dbgs() << "\t\ttaints local " << PrintReg(Other.Reg) << ':' 2329 << OtherI->valno->id << '@' << OtherI->start 2330 << " to " << End << '\n'); 2331 // A dead def is not a problem. 2332 if (End.isDead()) 2333 break; 2334 TaintExtent.push_back(std::make_pair(End, TaintedLanes)); 2335 2336 // Check for another def in the MBB. 2337 if (++OtherI == Other.LR.end() || OtherI->start >= MBBEnd) 2338 break; 2339 2340 // Lanes written by the new def are no longer tainted. 2341 const Val &OV = Other.Vals[OtherI->valno->id]; 2342 TaintedLanes &= ~OV.WriteLanes; 2343 if (!OV.RedefVNI) 2344 break; 2345 } while (TaintedLanes.any()); 2346 return true; 2347} 2348 2349bool JoinVals::usesLanes(const MachineInstr &MI, unsigned Reg, unsigned SubIdx, 2350 LaneBitmask Lanes) const { 2351 if (MI.isDebugValue()) 2352 return false; 2353 for (const MachineOperand &MO : MI.operands()) { 2354 if (!MO.isReg() || MO.isDef() || MO.getReg() != Reg) 2355 continue; 2356 if (!MO.readsReg()) 2357 continue; 2358 unsigned S = TRI->composeSubRegIndices(SubIdx, MO.getSubReg()); 2359 if ((Lanes & TRI->getSubRegIndexLaneMask(S)).any()) 2360 return true; 2361 } 2362 return false; 2363} 2364 2365bool JoinVals::resolveConflicts(JoinVals &Other) { 2366 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) { 2367 Val &V = Vals[i]; 2368 assert (V.Resolution != CR_Impossible && "Unresolvable conflict"); 2369 if (V.Resolution != CR_Unresolved) 2370 continue; 2371 DEBUG(dbgs() << "\t\tconflict at " << PrintReg(Reg) << ':' << i 2372 << '@' << LR.getValNumInfo(i)->def << '\n'); 2373 if (SubRangeJoin) 2374 return false; 2375 2376 ++NumLaneConflicts; 2377 assert(V.OtherVNI && "Inconsistent conflict resolution."); 2378 VNInfo *VNI = LR.getValNumInfo(i); 2379 const Val &OtherV = Other.Vals[V.OtherVNI->id]; 2380 2381 // VNI is known to clobber some lanes in OtherVNI. If we go ahead with the 2382 // join, those lanes will be tainted with a wrong value. Get the extent of 2383 // the tainted lanes. 2384 LaneBitmask TaintedLanes = V.WriteLanes & OtherV.ValidLanes; 2385 SmallVector<std::pair<SlotIndex, LaneBitmask>, 8> TaintExtent; 2386 if (!taintExtent(i, TaintedLanes, Other, TaintExtent)) 2387 // Tainted lanes would extend beyond the basic block. 2388 return false; 2389 2390 assert(!TaintExtent.empty() && "There should be at least one conflict."); 2391 2392 // Now look at the instructions from VNI->def to TaintExtent (inclusive). 2393 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 2394 MachineBasicBlock::iterator MI = MBB->begin(); 2395 if (!VNI->isPHIDef()) { 2396 MI = Indexes->getInstructionFromIndex(VNI->def); 2397 // No need to check the instruction defining VNI for reads. 2398 ++MI; 2399 } 2400 assert(!SlotIndex::isSameInstr(VNI->def, TaintExtent.front().first) && 2401 "Interference ends on VNI->def. Should have been handled earlier"); 2402 MachineInstr *LastMI = 2403 Indexes->getInstructionFromIndex(TaintExtent.front().first); 2404 assert(LastMI && "Range must end at a proper instruction"); 2405 unsigned TaintNum = 0; 2406 for (;;) { 2407 assert(MI != MBB->end() && "Bad LastMI"); 2408 if (usesLanes(*MI, Other.Reg, Other.SubIdx, TaintedLanes)) { 2409 DEBUG(dbgs() << "\t\ttainted lanes used by: " << *MI); 2410 return false; 2411 } 2412 // LastMI is the last instruction to use the current value. 2413 if (&*MI == LastMI) { 2414 if (++TaintNum == TaintExtent.size()) 2415 break; 2416 LastMI = Indexes->getInstructionFromIndex(TaintExtent[TaintNum].first); 2417 assert(LastMI && "Range must end at a proper instruction"); 2418 TaintedLanes = TaintExtent[TaintNum].second; 2419 } 2420 ++MI; 2421 } 2422 2423 // The tainted lanes are unused. 2424 V.Resolution = CR_Replace; 2425 ++NumLaneResolves; 2426 } 2427 return true; 2428} 2429 2430bool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) { 2431 Val &V = Vals[ValNo]; 2432 if (V.Pruned || V.PrunedComputed) 2433 return V.Pruned; 2434 2435 if (V.Resolution != CR_Erase && V.Resolution != CR_Merge) 2436 return V.Pruned; 2437 2438 // Follow copies up the dominator tree and check if any intermediate value 2439 // has been pruned. 2440 V.PrunedComputed = true; 2441 V.Pruned = Other.isPrunedValue(V.OtherVNI->id, *this); 2442 return V.Pruned; 2443} 2444 2445void JoinVals::pruneValues(JoinVals &Other, 2446 SmallVectorImpl<SlotIndex> &EndPoints, 2447 bool changeInstrs) { 2448 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) { 2449 SlotIndex Def = LR.getValNumInfo(i)->def; 2450 switch (Vals[i].Resolution) { 2451 case CR_Keep: 2452 break; 2453 case CR_Replace: { 2454 // This value takes precedence over the value in Other.LR. 2455 LIS->pruneValue(Other.LR, Def, &EndPoints); 2456 // Check if we're replacing an IMPLICIT_DEF value. The IMPLICIT_DEF 2457 // instructions are only inserted to provide a live-out value for PHI 2458 // predecessors, so the instruction should simply go away once its value 2459 // has been replaced. 2460 Val &OtherV = Other.Vals[Vals[i].OtherVNI->id]; 2461 bool EraseImpDef = OtherV.ErasableImplicitDef && 2462 OtherV.Resolution == CR_Keep; 2463 if (!Def.isBlock()) { 2464 if (changeInstrs) { 2465 // Remove <def,read-undef> flags. This def is now a partial redef. 2466 // Also remove <def,dead> flags since the joined live range will 2467 // continue past this instruction. 2468 for (MachineOperand &MO : 2469 Indexes->getInstructionFromIndex(Def)->operands()) { 2470 if (MO.isReg() && MO.isDef() && MO.getReg() == Reg) { 2471 if (MO.getSubReg() != 0) 2472 MO.setIsUndef(EraseImpDef); 2473 MO.setIsDead(false); 2474 } 2475 } 2476 } 2477 // This value will reach instructions below, but we need to make sure 2478 // the live range also reaches the instruction at Def. 2479 if (!EraseImpDef) 2480 EndPoints.push_back(Def); 2481 } 2482 DEBUG(dbgs() << "\t\tpruned " << PrintReg(Other.Reg) << " at " << Def 2483 << ": " << Other.LR << '\n'); 2484 break; 2485 } 2486 case CR_Erase: 2487 case CR_Merge: 2488 if (isPrunedValue(i, Other)) { 2489 // This value is ultimately a copy of a pruned value in LR or Other.LR. 2490 // We can no longer trust the value mapping computed by 2491 // computeAssignment(), the value that was originally copied could have 2492 // been replaced. 2493 LIS->pruneValue(LR, Def, &EndPoints); 2494 DEBUG(dbgs() << "\t\tpruned all of " << PrintReg(Reg) << " at " 2495 << Def << ": " << LR << '\n'); 2496 } 2497 break; 2498 case CR_Unresolved: 2499 case CR_Impossible: 2500 llvm_unreachable("Unresolved conflicts"); 2501 } 2502 } 2503} 2504 2505void JoinVals::pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask) { 2506 // Look for values being erased. 2507 bool DidPrune = false; 2508 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) { 2509 if (Vals[i].Resolution != CR_Erase) 2510 continue; 2511 2512 // Check subranges at the point where the copy will be removed. 2513 SlotIndex Def = LR.getValNumInfo(i)->def; 2514 for (LiveInterval::SubRange &S : LI.subranges()) { 2515 LiveQueryResult Q = S.Query(Def); 2516 2517 // If a subrange starts at the copy then an undefined value has been 2518 // copied and we must remove that subrange value as well. 2519 VNInfo *ValueOut = Q.valueOutOrDead(); 2520 if (ValueOut != nullptr && Q.valueIn() == nullptr) { 2521 DEBUG(dbgs() << "\t\tPrune sublane " << PrintLaneMask(S.LaneMask) 2522 << " at " << Def << "\n"); 2523 LIS->pruneValue(S, Def, nullptr); 2524 DidPrune = true; 2525 // Mark value number as unused. 2526 ValueOut->markUnused(); 2527 continue; 2528 } 2529 // If a subrange ends at the copy, then a value was copied but only 2530 // partially used later. Shrink the subregister range appropriately. 2531 if (Q.valueIn() != nullptr && Q.valueOut() == nullptr) { 2532 DEBUG(dbgs() << "\t\tDead uses at sublane " << PrintLaneMask(S.LaneMask) 2533 << " at " << Def << "\n"); 2534 ShrinkMask |= S.LaneMask; 2535 } 2536 } 2537 } 2538 if (DidPrune) 2539 LI.removeEmptySubRanges(); 2540} 2541 2542/// Check if any of the subranges of @p LI contain a definition at @p Def. 2543static bool isDefInSubRange(LiveInterval &LI, SlotIndex Def) { 2544 for (LiveInterval::SubRange &SR : LI.subranges()) { 2545 if (VNInfo *VNI = SR.Query(Def).valueOutOrDead()) 2546 if (VNI->def == Def) 2547 return true; 2548 } 2549 return false; 2550} 2551 2552void JoinVals::pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange) { 2553 assert(&static_cast<LiveRange&>(LI) == &LR); 2554 2555 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) { 2556 if (Vals[i].Resolution != CR_Keep) 2557 continue; 2558 VNInfo *VNI = LR.getValNumInfo(i); 2559 if (VNI->isUnused() || VNI->isPHIDef() || isDefInSubRange(LI, VNI->def)) 2560 continue; 2561 Vals[i].Pruned = true; 2562 ShrinkMainRange = true; 2563 } 2564} 2565 2566void JoinVals::removeImplicitDefs() { 2567 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) { 2568 Val &V = Vals[i]; 2569 if (V.Resolution != CR_Keep || !V.ErasableImplicitDef || !V.Pruned) 2570 continue; 2571 2572 VNInfo *VNI = LR.getValNumInfo(i); 2573 VNI->markUnused(); 2574 LR.removeValNo(VNI); 2575 } 2576} 2577 2578void JoinVals::eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs, 2579 SmallVectorImpl<unsigned> &ShrinkRegs, 2580 LiveInterval *LI) { 2581 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) { 2582 // Get the def location before markUnused() below invalidates it. 2583 SlotIndex Def = LR.getValNumInfo(i)->def; 2584 switch (Vals[i].Resolution) { 2585 case CR_Keep: { 2586 // If an IMPLICIT_DEF value is pruned, it doesn't serve a purpose any 2587 // longer. The IMPLICIT_DEF instructions are only inserted by 2588 // PHIElimination to guarantee that all PHI predecessors have a value. 2589 if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned) 2590 break; 2591 // Remove value number i from LR. 2592 // For intervals with subranges, removing a segment from the main range 2593 // may require extending the previous segment: for each definition of 2594 // a subregister, there will be a corresponding def in the main range. 2595 // That def may fall in the middle of a segment from another subrange. 2596 // In such cases, removing this def from the main range must be 2597 // complemented by extending the main range to account for the liveness 2598 // of the other subrange. 2599 VNInfo *VNI = LR.getValNumInfo(i); 2600 SlotIndex Def = VNI->def; 2601 // The new end point of the main range segment to be extended. 2602 SlotIndex NewEnd; 2603 if (LI != nullptr) { 2604 LiveRange::iterator I = LR.FindSegmentContaining(Def); 2605 assert(I != LR.end()); 2606 // Do not extend beyond the end of the segment being removed. 2607 // The segment may have been pruned in preparation for joining 2608 // live ranges. 2609 NewEnd = I->end; 2610 } 2611 2612 LR.removeValNo(VNI); 2613 // Note that this VNInfo is reused and still referenced in NewVNInfo, 2614 // make it appear like an unused value number. 2615 VNI->markUnused(); 2616 2617 if (LI != nullptr && LI->hasSubRanges()) { 2618 assert(static_cast<LiveRange*>(LI) == &LR); 2619 // Determine the end point based on the subrange information: 2620 // minimum of (earliest def of next segment, 2621 // latest end point of containing segment) 2622 SlotIndex ED, LE; 2623 for (LiveInterval::SubRange &SR : LI->subranges()) { 2624 LiveRange::iterator I = SR.find(Def); 2625 if (I == SR.end()) 2626 continue; 2627 if (I->start > Def) 2628 ED = ED.isValid() ? std::min(ED, I->start) : I->start; 2629 else 2630 LE = LE.isValid() ? std::max(LE, I->end) : I->end; 2631 } 2632 if (LE.isValid()) 2633 NewEnd = std::min(NewEnd, LE); 2634 if (ED.isValid()) 2635 NewEnd = std::min(NewEnd, ED); 2636 2637 // We only want to do the extension if there was a subrange that 2638 // was live across Def. 2639 if (LE.isValid()) { 2640 LiveRange::iterator S = LR.find(Def); 2641 if (S != LR.begin()) 2642 std::prev(S)->end = NewEnd; 2643 } 2644 } 2645 DEBUG({ 2646 dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LR << '\n'; 2647 if (LI != nullptr) 2648 dbgs() << "\t\t LHS = " << *LI << '\n'; 2649 }); 2650 LLVM_FALLTHROUGH; 2651 } 2652 2653 case CR_Erase: { 2654 MachineInstr *MI = Indexes->getInstructionFromIndex(Def); 2655 assert(MI && "No instruction to erase"); 2656 if (MI->isCopy()) { 2657 unsigned Reg = MI->getOperand(1).getReg(); 2658 if (TargetRegisterInfo::isVirtualRegister(Reg) && 2659 Reg != CP.getSrcReg() && Reg != CP.getDstReg()) 2660 ShrinkRegs.push_back(Reg); 2661 } 2662 ErasedInstrs.insert(MI); 2663 DEBUG(dbgs() << "\t\terased:\t" << Def << '\t' << *MI); 2664 LIS->RemoveMachineInstrFromMaps(*MI); 2665 MI->eraseFromParent(); 2666 break; 2667 } 2668 default: 2669 break; 2670 } 2671 } 2672} 2673 2674void RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, LiveRange &RRange, 2675 LaneBitmask LaneMask, 2676 const CoalescerPair &CP) { 2677 SmallVector<VNInfo*, 16> NewVNInfo; 2678 JoinVals RHSVals(RRange, CP.getSrcReg(), CP.getSrcIdx(), LaneMask, 2679 NewVNInfo, CP, LIS, TRI, true, true); 2680 JoinVals LHSVals(LRange, CP.getDstReg(), CP.getDstIdx(), LaneMask, 2681 NewVNInfo, CP, LIS, TRI, true, true); 2682 2683 // Compute NewVNInfo and resolve conflicts (see also joinVirtRegs()) 2684 // We should be able to resolve all conflicts here as we could successfully do 2685 // it on the mainrange already. There is however a problem when multiple 2686 // ranges get mapped to the "overflow" lane mask bit which creates unexpected 2687 // interferences. 2688 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) { 2689 // We already determined that it is legal to merge the intervals, so this 2690 // should never fail. 2691 llvm_unreachable("*** Couldn't join subrange!\n"); 2692 } 2693 if (!LHSVals.resolveConflicts(RHSVals) || 2694 !RHSVals.resolveConflicts(LHSVals)) { 2695 // We already determined that it is legal to merge the intervals, so this 2696 // should never fail. 2697 llvm_unreachable("*** Couldn't join subrange!\n"); 2698 } 2699 2700 // The merging algorithm in LiveInterval::join() can't handle conflicting 2701 // value mappings, so we need to remove any live ranges that overlap a 2702 // CR_Replace resolution. Collect a set of end points that can be used to 2703 // restore the live range after joining. 2704 SmallVector<SlotIndex, 8> EndPoints; 2705 LHSVals.pruneValues(RHSVals, EndPoints, false); 2706 RHSVals.pruneValues(LHSVals, EndPoints, false); 2707 2708 LHSVals.removeImplicitDefs(); 2709 RHSVals.removeImplicitDefs(); 2710 2711 LRange.verify(); 2712 RRange.verify(); 2713 2714 // Join RRange into LHS. 2715 LRange.join(RRange, LHSVals.getAssignments(), RHSVals.getAssignments(), 2716 NewVNInfo); 2717 2718 DEBUG(dbgs() << "\t\tjoined lanes: " << LRange << "\n"); 2719 if (EndPoints.empty()) 2720 return; 2721 2722 // Recompute the parts of the live range we had to remove because of 2723 // CR_Replace conflicts. 2724 DEBUG({ 2725 dbgs() << "\t\trestoring liveness to " << EndPoints.size() << " points: "; 2726 for (unsigned i = 0, n = EndPoints.size(); i != n; ++i) { 2727 dbgs() << EndPoints[i]; 2728 if (i != n-1) 2729 dbgs() << ','; 2730 } 2731 dbgs() << ": " << LRange << '\n'; 2732 }); 2733 LIS->extendToIndices(LRange, EndPoints); 2734} 2735 2736void RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI, 2737 const LiveRange &ToMerge, 2738 LaneBitmask LaneMask, 2739 CoalescerPair &CP) { 2740 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator(); 2741 for (LiveInterval::SubRange &R : LI.subranges()) { 2742 LaneBitmask RMask = R.LaneMask; 2743 // LaneMask of subregisters common to subrange R and ToMerge. 2744 LaneBitmask Common = RMask & LaneMask; 2745 // There is nothing to do without common subregs. 2746 if (Common.none()) 2747 continue; 2748 2749 DEBUG(dbgs() << "\t\tCopy+Merge " << PrintLaneMask(RMask) << " into " 2750 << PrintLaneMask(Common) << '\n'); 2751 // LaneMask of subregisters contained in the R range but not in ToMerge, 2752 // they have to split into their own subrange. 2753 LaneBitmask LRest = RMask & ~LaneMask; 2754 LiveInterval::SubRange *CommonRange; 2755 if (LRest.any()) { 2756 R.LaneMask = LRest; 2757 DEBUG(dbgs() << "\t\tReduce Lane to " << PrintLaneMask(LRest) << '\n'); 2758 // Duplicate SubRange for newly merged common stuff. 2759 CommonRange = LI.createSubRangeFrom(Allocator, Common, R); 2760 } else { 2761 // Reuse the existing range. 2762 R.LaneMask = Common; 2763 CommonRange = &R; 2764 } 2765 LiveRange RangeCopy(ToMerge, Allocator); 2766 joinSubRegRanges(*CommonRange, RangeCopy, Common, CP); 2767 LaneMask &= ~RMask; 2768 } 2769 2770 if (LaneMask.any()) { 2771 DEBUG(dbgs() << "\t\tNew Lane " << PrintLaneMask(LaneMask) << '\n'); 2772 LI.createSubRangeFrom(Allocator, LaneMask, ToMerge); 2773 } 2774} 2775 2776bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) { 2777 SmallVector<VNInfo*, 16> NewVNInfo; 2778 LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 2779 LiveInterval &LHS = LIS->getInterval(CP.getDstReg()); 2780 bool TrackSubRegLiveness = MRI->shouldTrackSubRegLiveness(*CP.getNewRC()); 2781 JoinVals RHSVals(RHS, CP.getSrcReg(), CP.getSrcIdx(), LaneBitmask::getNone(), 2782 NewVNInfo, CP, LIS, TRI, false, TrackSubRegLiveness); 2783 JoinVals LHSVals(LHS, CP.getDstReg(), CP.getDstIdx(), LaneBitmask::getNone(), 2784 NewVNInfo, CP, LIS, TRI, false, TrackSubRegLiveness); 2785 2786 DEBUG(dbgs() << "\t\tRHS = " << RHS 2787 << "\n\t\tLHS = " << LHS 2788 << '\n'); 2789 2790 // First compute NewVNInfo and the simple value mappings. 2791 // Detect impossible conflicts early. 2792 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) 2793 return false; 2794 2795 // Some conflicts can only be resolved after all values have been mapped. 2796 if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals)) 2797 return false; 2798 2799 // All clear, the live ranges can be merged. 2800 if (RHS.hasSubRanges() || LHS.hasSubRanges()) { 2801 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator(); 2802 2803 // Transform lanemasks from the LHS to masks in the coalesced register and 2804 // create initial subranges if necessary. 2805 unsigned DstIdx = CP.getDstIdx(); 2806 if (!LHS.hasSubRanges()) { 2807 LaneBitmask Mask = DstIdx == 0 ? CP.getNewRC()->getLaneMask() 2808 : TRI->getSubRegIndexLaneMask(DstIdx); 2809 // LHS must support subregs or we wouldn't be in this codepath. 2810 assert(Mask.any()); 2811 LHS.createSubRangeFrom(Allocator, Mask, LHS); 2812 } else if (DstIdx != 0) { 2813 // Transform LHS lanemasks to new register class if necessary. 2814 for (LiveInterval::SubRange &R : LHS.subranges()) { 2815 LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(DstIdx, R.LaneMask); 2816 R.LaneMask = Mask; 2817 } 2818 } 2819 DEBUG(dbgs() << "\t\tLHST = " << PrintReg(CP.getDstReg()) 2820 << ' ' << LHS << '\n'); 2821 2822 // Determine lanemasks of RHS in the coalesced register and merge subranges. 2823 unsigned SrcIdx = CP.getSrcIdx(); 2824 if (!RHS.hasSubRanges()) { 2825 LaneBitmask Mask = SrcIdx == 0 ? CP.getNewRC()->getLaneMask() 2826 : TRI->getSubRegIndexLaneMask(SrcIdx); 2827 mergeSubRangeInto(LHS, RHS, Mask, CP); 2828 } else { 2829 // Pair up subranges and merge. 2830 for (LiveInterval::SubRange &R : RHS.subranges()) { 2831 LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(SrcIdx, R.LaneMask); 2832 mergeSubRangeInto(LHS, R, Mask, CP); 2833 } 2834 } 2835 DEBUG(dbgs() << "\tJoined SubRanges " << LHS << "\n"); 2836 2837 // Pruning implicit defs from subranges may result in the main range 2838 // having stale segments. 2839 LHSVals.pruneMainSegments(LHS, ShrinkMainRange); 2840 2841 LHSVals.pruneSubRegValues(LHS, ShrinkMask); 2842 RHSVals.pruneSubRegValues(LHS, ShrinkMask); 2843 } 2844 2845 // The merging algorithm in LiveInterval::join() can't handle conflicting 2846 // value mappings, so we need to remove any live ranges that overlap a 2847 // CR_Replace resolution. Collect a set of end points that can be used to 2848 // restore the live range after joining. 2849 SmallVector<SlotIndex, 8> EndPoints; 2850 LHSVals.pruneValues(RHSVals, EndPoints, true); 2851 RHSVals.pruneValues(LHSVals, EndPoints, true); 2852 2853 // Erase COPY and IMPLICIT_DEF instructions. This may cause some external 2854 // registers to require trimming. 2855 SmallVector<unsigned, 8> ShrinkRegs; 2856 LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs, &LHS); 2857 RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs); 2858 while (!ShrinkRegs.empty()) 2859 shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val())); 2860 2861 // Join RHS into LHS. 2862 LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo); 2863 2864 // Kill flags are going to be wrong if the live ranges were overlapping. 2865 // Eventually, we should simply clear all kill flags when computing live 2866 // ranges. They are reinserted after register allocation. 2867 MRI->clearKillFlags(LHS.reg); 2868 MRI->clearKillFlags(RHS.reg); 2869 2870 if (!EndPoints.empty()) { 2871 // Recompute the parts of the live range we had to remove because of 2872 // CR_Replace conflicts. 2873 DEBUG({ 2874 dbgs() << "\t\trestoring liveness to " << EndPoints.size() << " points: "; 2875 for (unsigned i = 0, n = EndPoints.size(); i != n; ++i) { 2876 dbgs() << EndPoints[i]; 2877 if (i != n-1) 2878 dbgs() << ','; 2879 } 2880 dbgs() << ": " << LHS << '\n'; 2881 }); 2882 LIS->extendToIndices((LiveRange&)LHS, EndPoints); 2883 } 2884 2885 return true; 2886} 2887 2888bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) { 2889 return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP); 2890} 2891 2892namespace { 2893/// Information concerning MBB coalescing priority. 2894struct MBBPriorityInfo { 2895 MachineBasicBlock *MBB; 2896 unsigned Depth; 2897 bool IsSplit; 2898 2899 MBBPriorityInfo(MachineBasicBlock *mbb, unsigned depth, bool issplit) 2900 : MBB(mbb), Depth(depth), IsSplit(issplit) {} 2901}; 2902} 2903 2904/// C-style comparator that sorts first based on the loop depth of the basic 2905/// block (the unsigned), and then on the MBB number. 2906/// 2907/// EnableGlobalCopies assumes that the primary sort key is loop depth. 2908static int compareMBBPriority(const MBBPriorityInfo *LHS, 2909 const MBBPriorityInfo *RHS) { 2910 // Deeper loops first 2911 if (LHS->Depth != RHS->Depth) 2912 return LHS->Depth > RHS->Depth ? -1 : 1; 2913 2914 // Try to unsplit critical edges next. 2915 if (LHS->IsSplit != RHS->IsSplit) 2916 return LHS->IsSplit ? -1 : 1; 2917 2918 // Prefer blocks that are more connected in the CFG. This takes care of 2919 // the most difficult copies first while intervals are short. 2920 unsigned cl = LHS->MBB->pred_size() + LHS->MBB->succ_size(); 2921 unsigned cr = RHS->MBB->pred_size() + RHS->MBB->succ_size(); 2922 if (cl != cr) 2923 return cl > cr ? -1 : 1; 2924 2925 // As a last resort, sort by block number. 2926 return LHS->MBB->getNumber() < RHS->MBB->getNumber() ? -1 : 1; 2927} 2928 2929/// \returns true if the given copy uses or defines a local live range. 2930static bool isLocalCopy(MachineInstr *Copy, const LiveIntervals *LIS) { 2931 if (!Copy->isCopy()) 2932 return false; 2933 2934 if (Copy->getOperand(1).isUndef()) 2935 return false; 2936 2937 unsigned SrcReg = Copy->getOperand(1).getReg(); 2938 unsigned DstReg = Copy->getOperand(0).getReg(); 2939 if (TargetRegisterInfo::isPhysicalRegister(SrcReg) 2940 || TargetRegisterInfo::isPhysicalRegister(DstReg)) 2941 return false; 2942 2943 return LIS->intervalIsInOneMBB(LIS->getInterval(SrcReg)) 2944 || LIS->intervalIsInOneMBB(LIS->getInterval(DstReg)); 2945} 2946 2947bool RegisterCoalescer:: 2948copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList) { 2949 bool Progress = false; 2950 for (unsigned i = 0, e = CurrList.size(); i != e; ++i) { 2951 if (!CurrList[i]) 2952 continue; 2953 // Skip instruction pointers that have already been erased, for example by 2954 // dead code elimination. 2955 if (ErasedInstrs.erase(CurrList[i])) { 2956 CurrList[i] = nullptr; 2957 continue; 2958 } 2959 bool Again = false; 2960 bool Success = joinCopy(CurrList[i], Again); 2961 Progress |= Success; 2962 if (Success || !Again) 2963 CurrList[i] = nullptr; 2964 } 2965 return Progress; 2966} 2967 2968/// Check if DstReg is a terminal node. 2969/// I.e., it does not have any affinity other than \p Copy. 2970static bool isTerminalReg(unsigned DstReg, const MachineInstr &Copy, 2971 const MachineRegisterInfo *MRI) { 2972 assert(Copy.isCopyLike()); 2973 // Check if the destination of this copy as any other affinity. 2974 for (const MachineInstr &MI : MRI->reg_nodbg_instructions(DstReg)) 2975 if (&MI != &Copy && MI.isCopyLike()) 2976 return false; 2977 return true; 2978} 2979 2980bool RegisterCoalescer::applyTerminalRule(const MachineInstr &Copy) const { 2981 assert(Copy.isCopyLike()); 2982 if (!UseTerminalRule) 2983 return false; 2984 unsigned DstReg, DstSubReg, SrcReg, SrcSubReg; 2985 isMoveInstr(*TRI, &Copy, SrcReg, DstReg, SrcSubReg, DstSubReg); 2986 // Check if the destination of this copy has any other affinity. 2987 if (TargetRegisterInfo::isPhysicalRegister(DstReg) || 2988 // If SrcReg is a physical register, the copy won't be coalesced. 2989 // Ignoring it may have other side effect (like missing 2990 // rematerialization). So keep it. 2991 TargetRegisterInfo::isPhysicalRegister(SrcReg) || 2992 !isTerminalReg(DstReg, Copy, MRI)) 2993 return false; 2994 2995 // DstReg is a terminal node. Check if it interferes with any other 2996 // copy involving SrcReg. 2997 const MachineBasicBlock *OrigBB = Copy.getParent(); 2998 const LiveInterval &DstLI = LIS->getInterval(DstReg); 2999 for (const MachineInstr &MI : MRI->reg_nodbg_instructions(SrcReg)) { 3000 // Technically we should check if the weight of the new copy is 3001 // interesting compared to the other one and update the weight 3002 // of the copies accordingly. However, this would only work if 3003 // we would gather all the copies first then coalesce, whereas 3004 // right now we interleave both actions. 3005 // For now, just consider the copies that are in the same block. 3006 if (&MI == &Copy || !MI.isCopyLike() || MI.getParent() != OrigBB) 3007 continue; 3008 unsigned OtherReg, OtherSubReg, OtherSrcReg, OtherSrcSubReg; 3009 isMoveInstr(*TRI, &Copy, OtherSrcReg, OtherReg, OtherSrcSubReg, 3010 OtherSubReg); 3011 if (OtherReg == SrcReg) 3012 OtherReg = OtherSrcReg; 3013 // Check if OtherReg is a non-terminal. 3014 if (TargetRegisterInfo::isPhysicalRegister(OtherReg) || 3015 isTerminalReg(OtherReg, MI, MRI)) 3016 continue; 3017 // Check that OtherReg interfere with DstReg. 3018 if (LIS->getInterval(OtherReg).overlaps(DstLI)) { 3019 DEBUG(dbgs() << "Apply terminal rule for: " << PrintReg(DstReg) << '\n'); 3020 return true; 3021 } 3022 } 3023 return false; 3024} 3025 3026void 3027RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) { 3028 DEBUG(dbgs() << MBB->getName() << ":\n"); 3029 3030 // Collect all copy-like instructions in MBB. Don't start coalescing anything 3031 // yet, it might invalidate the iterator. 3032 const unsigned PrevSize = WorkList.size(); 3033 if (JoinGlobalCopies) { 3034 SmallVector<MachineInstr*, 2> LocalTerminals; 3035 SmallVector<MachineInstr*, 2> GlobalTerminals; 3036 // Coalesce copies bottom-up to coalesce local defs before local uses. They 3037 // are not inherently easier to resolve, but slightly preferable until we 3038 // have local live range splitting. In particular this is required by 3039 // cmp+jmp macro fusion. 3040 for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 3041 MII != E; ++MII) { 3042 if (!MII->isCopyLike()) 3043 continue; 3044 bool ApplyTerminalRule = applyTerminalRule(*MII); 3045 if (isLocalCopy(&(*MII), LIS)) { 3046 if (ApplyTerminalRule) 3047 LocalTerminals.push_back(&(*MII)); 3048 else 3049 LocalWorkList.push_back(&(*MII)); 3050 } else { 3051 if (ApplyTerminalRule) 3052 GlobalTerminals.push_back(&(*MII)); 3053 else 3054 WorkList.push_back(&(*MII)); 3055 } 3056 } 3057 // Append the copies evicted by the terminal rule at the end of the list. 3058 LocalWorkList.append(LocalTerminals.begin(), LocalTerminals.end()); 3059 WorkList.append(GlobalTerminals.begin(), GlobalTerminals.end()); 3060 } 3061 else { 3062 SmallVector<MachineInstr*, 2> Terminals; 3063 for (MachineInstr &MII : *MBB) 3064 if (MII.isCopyLike()) { 3065 if (applyTerminalRule(MII)) 3066 Terminals.push_back(&MII); 3067 else 3068 WorkList.push_back(&MII); 3069 } 3070 // Append the copies evicted by the terminal rule at the end of the list. 3071 WorkList.append(Terminals.begin(), Terminals.end()); 3072 } 3073 // Try coalescing the collected copies immediately, and remove the nulls. 3074 // This prevents the WorkList from getting too large since most copies are 3075 // joinable on the first attempt. 3076 MutableArrayRef<MachineInstr*> 3077 CurrList(WorkList.begin() + PrevSize, WorkList.end()); 3078 if (copyCoalesceWorkList(CurrList)) 3079 WorkList.erase(std::remove(WorkList.begin() + PrevSize, WorkList.end(), 3080 (MachineInstr*)nullptr), WorkList.end()); 3081} 3082 3083void RegisterCoalescer::coalesceLocals() { 3084 copyCoalesceWorkList(LocalWorkList); 3085 for (unsigned j = 0, je = LocalWorkList.size(); j != je; ++j) { 3086 if (LocalWorkList[j]) 3087 WorkList.push_back(LocalWorkList[j]); 3088 } 3089 LocalWorkList.clear(); 3090} 3091 3092void RegisterCoalescer::joinAllIntervals() { 3093 DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n"); 3094 assert(WorkList.empty() && LocalWorkList.empty() && "Old data still around."); 3095 3096 std::vector<MBBPriorityInfo> MBBs; 3097 MBBs.reserve(MF->size()); 3098 for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E; ++I) { 3099 MachineBasicBlock *MBB = &*I; 3100 MBBs.push_back(MBBPriorityInfo(MBB, Loops->getLoopDepth(MBB), 3101 JoinSplitEdges && isSplitEdge(MBB))); 3102 } 3103 array_pod_sort(MBBs.begin(), MBBs.end(), compareMBBPriority); 3104 3105 // Coalesce intervals in MBB priority order. 3106 unsigned CurrDepth = UINT_MAX; 3107 for (unsigned i = 0, e = MBBs.size(); i != e; ++i) { 3108 // Try coalescing the collected local copies for deeper loops. 3109 if (JoinGlobalCopies && MBBs[i].Depth < CurrDepth) { 3110 coalesceLocals(); 3111 CurrDepth = MBBs[i].Depth; 3112 } 3113 copyCoalesceInMBB(MBBs[i].MBB); 3114 } 3115 coalesceLocals(); 3116 3117 // Joining intervals can allow other intervals to be joined. Iteratively join 3118 // until we make no progress. 3119 while (copyCoalesceWorkList(WorkList)) 3120 /* empty */ ; 3121} 3122 3123void RegisterCoalescer::releaseMemory() { 3124 ErasedInstrs.clear(); 3125 WorkList.clear(); 3126 DeadDefs.clear(); 3127 InflateRegs.clear(); 3128} 3129 3130bool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) { 3131 MF = &fn; 3132 MRI = &fn.getRegInfo(); 3133 TM = &fn.getTarget(); 3134 const TargetSubtargetInfo &STI = fn.getSubtarget(); 3135 TRI = STI.getRegisterInfo(); 3136 TII = STI.getInstrInfo(); 3137 LIS = &getAnalysis<LiveIntervals>(); 3138 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 3139 Loops = &getAnalysis<MachineLoopInfo>(); 3140 if (EnableGlobalCopies == cl::BOU_UNSET) 3141 JoinGlobalCopies = STI.enableJoinGlobalCopies(); 3142 else 3143 JoinGlobalCopies = (EnableGlobalCopies == cl::BOU_TRUE); 3144 3145 // The MachineScheduler does not currently require JoinSplitEdges. This will 3146 // either be enabled unconditionally or replaced by a more general live range 3147 // splitting optimization. 3148 JoinSplitEdges = EnableJoinSplits; 3149 3150 DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n" 3151 << "********** Function: " << MF->getName() << '\n'); 3152 3153 if (VerifyCoalescing) 3154 MF->verify(this, "Before register coalescing"); 3155 3156 RegClassInfo.runOnMachineFunction(fn); 3157 3158 // Join (coalesce) intervals if requested. 3159 if (EnableJoining) 3160 joinAllIntervals(); 3161 3162 // After deleting a lot of copies, register classes may be less constrained. 3163 // Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 -> 3164 // DPR inflation. 3165 array_pod_sort(InflateRegs.begin(), InflateRegs.end()); 3166 InflateRegs.erase(std::unique(InflateRegs.begin(), InflateRegs.end()), 3167 InflateRegs.end()); 3168 DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size() << " regs.\n"); 3169 for (unsigned i = 0, e = InflateRegs.size(); i != e; ++i) { 3170 unsigned Reg = InflateRegs[i]; 3171 if (MRI->reg_nodbg_empty(Reg)) 3172 continue; 3173 if (MRI->recomputeRegClass(Reg)) { 3174 DEBUG(dbgs() << PrintReg(Reg) << " inflated to " 3175 << TRI->getRegClassName(MRI->getRegClass(Reg)) << '\n'); 3176 ++NumInflated; 3177 3178 LiveInterval &LI = LIS->getInterval(Reg); 3179 if (LI.hasSubRanges()) { 3180 // If the inflated register class does not support subregisters anymore 3181 // remove the subranges. 3182 if (!MRI->shouldTrackSubRegLiveness(Reg)) { 3183 LI.clearSubRanges(); 3184 } else { 3185#ifndef NDEBUG 3186 LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(Reg); 3187 // If subranges are still supported, then the same subregs 3188 // should still be supported. 3189 for (LiveInterval::SubRange &S : LI.subranges()) { 3190 assert((S.LaneMask & ~MaxMask).none()); 3191 } 3192#endif 3193 } 3194 } 3195 } 3196 } 3197 3198 DEBUG(dump()); 3199 if (VerifyCoalescing) 3200 MF->verify(this, "After register coalescing"); 3201 return true; 3202} 3203 3204void RegisterCoalescer::print(raw_ostream &O, const Module* m) const { 3205 LIS->print(O, m); 3206} 3207