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