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