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