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