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