1 //===- RegisterCoalescer.cpp - Generic Register Coalescing Interface -------==// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the generic RegisterCoalescer interface which 11 // is used as the common interface used by all clients and 12 // implementations of register coalescing. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #include "RegisterCoalescer.h" 17 #include "llvm/ADT/STLExtras.h" 18 #include "llvm/ADT/SmallSet.h" 19 #include "llvm/ADT/Statistic.h" 20 #include "llvm/Analysis/AliasAnalysis.h" 21 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 22 #include "llvm/CodeGen/LiveRangeEdit.h" 23 #include "llvm/CodeGen/MachineFrameInfo.h" 24 #include "llvm/CodeGen/MachineInstr.h" 25 #include "llvm/CodeGen/MachineLoopInfo.h" 26 #include "llvm/CodeGen/MachineRegisterInfo.h" 27 #include "llvm/CodeGen/Passes.h" 28 #include "llvm/CodeGen/RegisterClassInfo.h" 29 #include "llvm/CodeGen/VirtRegMap.h" 30 #include "llvm/IR/Value.h" 31 #include "llvm/Pass.h" 32 #include "llvm/Support/CommandLine.h" 33 #include "llvm/Support/Debug.h" 34 #include "llvm/Support/ErrorHandling.h" 35 #include "llvm/Support/raw_ostream.h" 36 #include "llvm/Target/TargetInstrInfo.h" 37 #include "llvm/Target/TargetMachine.h" 38 #include "llvm/Target/TargetRegisterInfo.h" 39 #include "llvm/Target/TargetSubtargetInfo.h" 40 #include <algorithm> 41 #include <cmath> 42 using namespace llvm; 43 44 #define DEBUG_TYPE "regalloc" 45 46 STATISTIC(numJoins , "Number of interval joins performed"); 47 STATISTIC(numCrossRCs , "Number of cross class joins performed"); 48 STATISTIC(numCommutes , "Number of instruction commuting performed"); 49 STATISTIC(numExtends , "Number of copies extended"); 50 STATISTIC(NumReMats , "Number of instructions re-materialized"); 51 STATISTIC(NumInflated , "Number of register classes inflated"); 52 STATISTIC(NumLaneConflicts, "Number of dead lane conflicts tested"); 53 STATISTIC(NumLaneResolves, "Number of dead lane conflicts resolved"); 54 55 static cl::opt<bool> 56 EnableJoining("join-liveintervals", 57 cl::desc("Coalesce copies (default=true)"), 58 cl::init(true)); 59 60 // Temporary flag to test critical edge unsplitting. 61 static cl::opt<bool> 62 EnableJoinSplits("join-splitedges", 63 cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden); 64 65 // Temporary flag to test global copy optimization. 66 static cl::opt<cl::boolOrDefault> 67 EnableGlobalCopies("join-globalcopies", 68 cl::desc("Coalesce copies that span blocks (default=subtarget)"), 69 cl::init(cl::BOU_UNSET), cl::Hidden); 70 71 static cl::opt<bool> 72 VerifyCoalescing("verify-coalescing", 73 cl::desc("Verify machine instrs before and after register coalescing"), 74 cl::Hidden); 75 76 namespace { 77 class RegisterCoalescer : public MachineFunctionPass, 78 private LiveRangeEdit::Delegate { 79 MachineFunction* MF; 80 MachineRegisterInfo* MRI; 81 const TargetMachine* TM; 82 const TargetRegisterInfo* TRI; 83 const TargetInstrInfo* TII; 84 LiveIntervals *LIS; 85 const MachineLoopInfo* Loops; 86 AliasAnalysis *AA; 87 RegisterClassInfo RegClassInfo; 88 89 /// \brief True if the coalescer should aggressively coalesce global copies 90 /// in favor of keeping local copies. 91 bool JoinGlobalCopies; 92 93 /// \brief True if the coalescer should aggressively coalesce fall-thru 94 /// blocks exclusively containing copies. 95 bool JoinSplitEdges; 96 97 /// WorkList - Copy instructions yet to be coalesced. 98 SmallVector<MachineInstr*, 8> WorkList; 99 SmallVector<MachineInstr*, 8> LocalWorkList; 100 101 /// ErasedInstrs - Set of instruction pointers that have been erased, and 102 /// that may be present in WorkList. 103 SmallPtrSet<MachineInstr*, 8> ErasedInstrs; 104 105 /// Dead instructions that are about to be deleted. 106 SmallVector<MachineInstr*, 8> DeadDefs; 107 108 /// Virtual registers to be considered for register class inflation. 109 SmallVector<unsigned, 8> InflateRegs; 110 111 /// Recursively eliminate dead defs in DeadDefs. 112 void eliminateDeadDefs(); 113 114 /// LiveRangeEdit callback. 115 void LRE_WillEraseInstruction(MachineInstr *MI) override; 116 117 /// coalesceLocals - coalesce the LocalWorkList. 118 void coalesceLocals(); 119 120 /// joinAllIntervals - join compatible live intervals 121 void joinAllIntervals(); 122 123 /// copyCoalesceInMBB - Coalesce copies in the specified MBB, putting 124 /// copies that cannot yet be coalesced into WorkList. 125 void copyCoalesceInMBB(MachineBasicBlock *MBB); 126 127 /// copyCoalesceWorkList - Try to coalesce all copies in CurrList. Return 128 /// true if any progress was made. 129 bool copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList); 130 131 /// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 132 /// which are the src/dst of the copy instruction CopyMI. This returns 133 /// true if the copy was successfully coalesced away. If it is not 134 /// currently possible to coalesce this interval, but it may be possible if 135 /// other things get coalesced, then it returns true by reference in 136 /// 'Again'. 137 bool joinCopy(MachineInstr *TheCopy, bool &Again); 138 139 /// joinIntervals - Attempt to join these two intervals. On failure, this 140 /// returns false. The output "SrcInt" will not have been modified, so we 141 /// can use this information below to update aliases. 142 bool joinIntervals(CoalescerPair &CP); 143 144 /// Attempt joining two virtual registers. Return true on success. 145 bool joinVirtRegs(CoalescerPair &CP); 146 147 /// Attempt joining with a reserved physreg. 148 bool joinReservedPhysReg(CoalescerPair &CP); 149 150 /// adjustCopiesBackFrom - We found a non-trivially-coalescable copy. If 151 /// the source value number is defined by a copy from the destination reg 152 /// see if we can merge these two destination reg valno# into a single 153 /// value number, eliminating a copy. 154 bool adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI); 155 156 /// hasOtherReachingDefs - Return true if there are definitions of IntB 157 /// other than BValNo val# that can reach uses of AValno val# of IntA. 158 bool hasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB, 159 VNInfo *AValNo, VNInfo *BValNo); 160 161 /// removeCopyByCommutingDef - We found a non-trivially-coalescable copy. 162 /// If the source value number is defined by a commutable instruction and 163 /// its other operand is coalesced to the copy dest register, see if we 164 /// can transform the copy into a noop by commuting the definition. 165 bool removeCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI); 166 167 /// reMaterializeTrivialDef - If the source of a copy is defined by a 168 /// trivial computation, replace the copy by rematerialize the definition. 169 bool reMaterializeTrivialDef(CoalescerPair &CP, MachineInstr *CopyMI, 170 bool &IsDefCopy); 171 172 /// canJoinPhys - Return true if a physreg copy should be joined. 173 bool canJoinPhys(const CoalescerPair &CP); 174 175 /// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 176 /// update the subregister number if it is not zero. If DstReg is a 177 /// physical register and the existing subregister number of the def / use 178 /// being updated is not zero, make sure to set it to the correct physical 179 /// subregister. 180 void updateRegDefsUses(unsigned SrcReg, unsigned DstReg, unsigned SubIdx); 181 182 /// eliminateUndefCopy - Handle copies of undef values. 183 bool eliminateUndefCopy(MachineInstr *CopyMI, const CoalescerPair &CP); 184 185 public: 186 static char ID; // Class identification, replacement for typeinfo 187 RegisterCoalescer() : MachineFunctionPass(ID) { 188 initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 189 } 190 191 void getAnalysisUsage(AnalysisUsage &AU) const override; 192 193 void releaseMemory() override; 194 195 /// runOnMachineFunction - pass entry point 196 bool runOnMachineFunction(MachineFunction&) override; 197 198 /// print - Implement the dump method. 199 void print(raw_ostream &O, const Module* = nullptr) const override; 200 }; 201 } /// end anonymous namespace 202 203 char &llvm::RegisterCoalescerID = RegisterCoalescer::ID; 204 205 INITIALIZE_PASS_BEGIN(RegisterCoalescer, "simple-register-coalescing", 206 "Simple Register Coalescing", false, false) 207 INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 208 INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 209 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 210 INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 211 INITIALIZE_PASS_END(RegisterCoalescer, "simple-register-coalescing", 212 "Simple Register Coalescing", false, false) 213 214 char RegisterCoalescer::ID = 0; 215 216 static bool isMoveInstr(const TargetRegisterInfo &tri, const MachineInstr *MI, 217 unsigned &Src, unsigned &Dst, 218 unsigned &SrcSub, unsigned &DstSub) { 219 if (MI->isCopy()) { 220 Dst = MI->getOperand(0).getReg(); 221 DstSub = MI->getOperand(0).getSubReg(); 222 Src = MI->getOperand(1).getReg(); 223 SrcSub = MI->getOperand(1).getSubReg(); 224 } else if (MI->isSubregToReg()) { 225 Dst = MI->getOperand(0).getReg(); 226 DstSub = tri.composeSubRegIndices(MI->getOperand(0).getSubReg(), 227 MI->getOperand(3).getImm()); 228 Src = MI->getOperand(2).getReg(); 229 SrcSub = MI->getOperand(2).getSubReg(); 230 } else 231 return false; 232 return true; 233 } 234 235 // Return true if this block should be vacated by the coalescer to eliminate 236 // branches. The important cases to handle in the coalescer are critical edges 237 // split during phi elimination which contain only copies. Simple blocks that 238 // contain non-branches should also be vacated, but this can be handled by an 239 // earlier pass similar to early if-conversion. 240 static bool isSplitEdge(const MachineBasicBlock *MBB) { 241 if (MBB->pred_size() != 1 || MBB->succ_size() != 1) 242 return false; 243 244 for (const auto &MI : *MBB) { 245 if (!MI.isCopyLike() && !MI.isUnconditionalBranch()) 246 return false; 247 } 248 return true; 249 } 250 251 bool CoalescerPair::setRegisters(const MachineInstr *MI) { 252 SrcReg = DstReg = 0; 253 SrcIdx = DstIdx = 0; 254 NewRC = nullptr; 255 Flipped = CrossClass = false; 256 257 unsigned Src, Dst, SrcSub, DstSub; 258 if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 259 return false; 260 Partial = SrcSub || DstSub; 261 262 // If one register is a physreg, it must be Dst. 263 if (TargetRegisterInfo::isPhysicalRegister(Src)) { 264 if (TargetRegisterInfo::isPhysicalRegister(Dst)) 265 return false; 266 std::swap(Src, Dst); 267 std::swap(SrcSub, DstSub); 268 Flipped = true; 269 } 270 271 const MachineRegisterInfo &MRI = MI->getParent()->getParent()->getRegInfo(); 272 273 if (TargetRegisterInfo::isPhysicalRegister(Dst)) { 274 // Eliminate DstSub on a physreg. 275 if (DstSub) { 276 Dst = TRI.getSubReg(Dst, DstSub); 277 if (!Dst) return false; 278 DstSub = 0; 279 } 280 281 // Eliminate SrcSub by picking a corresponding Dst superregister. 282 if (SrcSub) { 283 Dst = TRI.getMatchingSuperReg(Dst, SrcSub, MRI.getRegClass(Src)); 284 if (!Dst) return false; 285 } else if (!MRI.getRegClass(Src)->contains(Dst)) { 286 return false; 287 } 288 } else { 289 // Both registers are virtual. 290 const TargetRegisterClass *SrcRC = MRI.getRegClass(Src); 291 const TargetRegisterClass *DstRC = MRI.getRegClass(Dst); 292 293 // Both registers have subreg indices. 294 if (SrcSub && DstSub) { 295 // Copies between different sub-registers are never coalescable. 296 if (Src == Dst && SrcSub != DstSub) 297 return false; 298 299 NewRC = TRI.getCommonSuperRegClass(SrcRC, SrcSub, DstRC, DstSub, 300 SrcIdx, DstIdx); 301 if (!NewRC) 302 return false; 303 } else if (DstSub) { 304 // SrcReg will be merged with a sub-register of DstReg. 305 SrcIdx = DstSub; 306 NewRC = TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub); 307 } else if (SrcSub) { 308 // DstReg will be merged with a sub-register of SrcReg. 309 DstIdx = SrcSub; 310 NewRC = TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSub); 311 } else { 312 // This is a straight copy without sub-registers. 313 NewRC = TRI.getCommonSubClass(DstRC, SrcRC); 314 } 315 316 // The combined constraint may be impossible to satisfy. 317 if (!NewRC) 318 return false; 319 320 // Prefer SrcReg to be a sub-register of DstReg. 321 // FIXME: Coalescer should support subregs symmetrically. 322 if (DstIdx && !SrcIdx) { 323 std::swap(Src, Dst); 324 std::swap(SrcIdx, DstIdx); 325 Flipped = !Flipped; 326 } 327 328 CrossClass = NewRC != DstRC || NewRC != SrcRC; 329 } 330 // Check our invariants 331 assert(TargetRegisterInfo::isVirtualRegister(Src) && "Src must be virtual"); 332 assert(!(TargetRegisterInfo::isPhysicalRegister(Dst) && DstSub) && 333 "Cannot have a physical SubIdx"); 334 SrcReg = Src; 335 DstReg = Dst; 336 return true; 337 } 338 339 bool CoalescerPair::flip() { 340 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) 341 return false; 342 std::swap(SrcReg, DstReg); 343 std::swap(SrcIdx, DstIdx); 344 Flipped = !Flipped; 345 return true; 346 } 347 348 bool CoalescerPair::isCoalescable(const MachineInstr *MI) const { 349 if (!MI) 350 return false; 351 unsigned Src, Dst, SrcSub, DstSub; 352 if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 353 return false; 354 355 // Find the virtual register that is SrcReg. 356 if (Dst == SrcReg) { 357 std::swap(Src, Dst); 358 std::swap(SrcSub, DstSub); 359 } else if (Src != SrcReg) { 360 return false; 361 } 362 363 // Now check that Dst matches DstReg. 364 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { 365 if (!TargetRegisterInfo::isPhysicalRegister(Dst)) 366 return false; 367 assert(!DstIdx && !SrcIdx && "Inconsistent CoalescerPair state."); 368 // DstSub could be set for a physreg from INSERT_SUBREG. 369 if (DstSub) 370 Dst = TRI.getSubReg(Dst, DstSub); 371 // Full copy of Src. 372 if (!SrcSub) 373 return DstReg == Dst; 374 // This is a partial register copy. Check that the parts match. 375 return TRI.getSubReg(DstReg, SrcSub) == Dst; 376 } else { 377 // DstReg is virtual. 378 if (DstReg != Dst) 379 return false; 380 // Registers match, do the subregisters line up? 381 return TRI.composeSubRegIndices(SrcIdx, SrcSub) == 382 TRI.composeSubRegIndices(DstIdx, DstSub); 383 } 384 } 385 386 void RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const { 387 AU.setPreservesCFG(); 388 AU.addRequired<AliasAnalysis>(); 389 AU.addRequired<LiveIntervals>(); 390 AU.addPreserved<LiveIntervals>(); 391 AU.addPreserved<SlotIndexes>(); 392 AU.addRequired<MachineLoopInfo>(); 393 AU.addPreserved<MachineLoopInfo>(); 394 AU.addPreservedID(MachineDominatorsID); 395 MachineFunctionPass::getAnalysisUsage(AU); 396 } 397 398 void RegisterCoalescer::eliminateDeadDefs() { 399 SmallVector<unsigned, 8> NewRegs; 400 LiveRangeEdit(nullptr, NewRegs, *MF, *LIS, 401 nullptr, this).eliminateDeadDefs(DeadDefs); 402 } 403 404 // Callback from eliminateDeadDefs(). 405 void RegisterCoalescer::LRE_WillEraseInstruction(MachineInstr *MI) { 406 // MI may be in WorkList. Make sure we don't visit it. 407 ErasedInstrs.insert(MI); 408 } 409 410 /// adjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA 411 /// being the source and IntB being the dest, thus this defines a value number 412 /// in IntB. If the source value number (in IntA) is defined by a copy from B, 413 /// see if we can merge these two pieces of B into a single value number, 414 /// eliminating a copy. For example: 415 /// 416 /// A3 = B0 417 /// ... 418 /// B1 = A3 <- this copy 419 /// 420 /// In this case, B0 can be extended to where the B1 copy lives, allowing the B1 421 /// value number to be replaced with B0 (which simplifies the B liveinterval). 422 /// 423 /// This returns true if an interval was modified. 424 /// 425 bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP, 426 MachineInstr *CopyMI) { 427 assert(!CP.isPartial() && "This doesn't work for partial copies."); 428 assert(!CP.isPhys() && "This doesn't work for physreg copies."); 429 430 LiveInterval &IntA = 431 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 432 LiveInterval &IntB = 433 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 434 SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 435 436 // BValNo is a value number in B that is defined by a copy from A. 'B1' in 437 // the example above. 438 LiveInterval::iterator BS = IntB.FindSegmentContaining(CopyIdx); 439 if (BS == IntB.end()) return false; 440 VNInfo *BValNo = BS->valno; 441 442 // Get the location that B is defined at. Two options: either this value has 443 // an unknown definition point or it is defined at CopyIdx. If unknown, we 444 // can't process it. 445 if (BValNo->def != CopyIdx) return false; 446 447 // AValNo is the value number in A that defines the copy, A3 in the example. 448 SlotIndex CopyUseIdx = CopyIdx.getRegSlot(true); 449 LiveInterval::iterator AS = IntA.FindSegmentContaining(CopyUseIdx); 450 // The live segment might not exist after fun with physreg coalescing. 451 if (AS == IntA.end()) return false; 452 VNInfo *AValNo = AS->valno; 453 454 // If AValNo is defined as a copy from IntB, we can potentially process this. 455 // Get the instruction that defines this value number. 456 MachineInstr *ACopyMI = LIS->getInstructionFromIndex(AValNo->def); 457 // Don't allow any partial copies, even if isCoalescable() allows them. 458 if (!CP.isCoalescable(ACopyMI) || !ACopyMI->isFullCopy()) 459 return false; 460 461 // Get the Segment in IntB that this value number starts with. 462 LiveInterval::iterator ValS = 463 IntB.FindSegmentContaining(AValNo->def.getPrevSlot()); 464 if (ValS == IntB.end()) 465 return false; 466 467 // Make sure that the end of the live segment is inside the same block as 468 // CopyMI. 469 MachineInstr *ValSEndInst = 470 LIS->getInstructionFromIndex(ValS->end.getPrevSlot()); 471 if (!ValSEndInst || ValSEndInst->getParent() != CopyMI->getParent()) 472 return false; 473 474 // Okay, we now know that ValS ends in the same block that the CopyMI 475 // live-range starts. If there are no intervening live segments between them 476 // in IntB, we can merge them. 477 if (ValS+1 != BS) return false; 478 479 DEBUG(dbgs() << "Extending: " << PrintReg(IntB.reg, TRI)); 480 481 SlotIndex FillerStart = ValS->end, FillerEnd = BS->start; 482 // We are about to delete CopyMI, so need to remove it as the 'instruction 483 // that defines this value #'. Update the valnum with the new defining 484 // instruction #. 485 BValNo->def = FillerStart; 486 487 // Okay, we can merge them. We need to insert a new liverange: 488 // [ValS.end, BS.begin) of either value number, then we merge the 489 // two value numbers. 490 IntB.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, BValNo)); 491 492 // Okay, merge "B1" into the same value number as "B0". 493 if (BValNo != ValS->valno) 494 IntB.MergeValueNumberInto(BValNo, ValS->valno); 495 DEBUG(dbgs() << " result = " << IntB << '\n'); 496 497 // If the source instruction was killing the source register before the 498 // merge, unset the isKill marker given the live range has been extended. 499 int UIdx = ValSEndInst->findRegisterUseOperandIdx(IntB.reg, true); 500 if (UIdx != -1) { 501 ValSEndInst->getOperand(UIdx).setIsKill(false); 502 } 503 504 // Rewrite the copy. If the copy instruction was killing the destination 505 // register before the merge, find the last use and trim the live range. That 506 // will also add the isKill marker. 507 CopyMI->substituteRegister(IntA.reg, IntB.reg, 0, *TRI); 508 if (AS->end == CopyIdx) 509 LIS->shrinkToUses(&IntA); 510 511 ++numExtends; 512 return true; 513 } 514 515 /// hasOtherReachingDefs - Return true if there are definitions of IntB 516 /// other than BValNo val# that can reach uses of AValno val# of IntA. 517 bool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA, 518 LiveInterval &IntB, 519 VNInfo *AValNo, 520 VNInfo *BValNo) { 521 // If AValNo has PHI kills, conservatively assume that IntB defs can reach 522 // the PHI values. 523 if (LIS->hasPHIKill(IntA, AValNo)) 524 return true; 525 526 for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 527 AI != AE; ++AI) { 528 if (AI->valno != AValNo) continue; 529 LiveInterval::iterator BI = 530 std::upper_bound(IntB.begin(), IntB.end(), AI->start); 531 if (BI != IntB.begin()) 532 --BI; 533 for (; BI != IntB.end() && AI->end >= BI->start; ++BI) { 534 if (BI->valno == BValNo) 535 continue; 536 if (BI->start <= AI->start && BI->end > AI->start) 537 return true; 538 if (BI->start > AI->start && BI->start < AI->end) 539 return true; 540 } 541 } 542 return false; 543 } 544 545 /// removeCopyByCommutingDef - We found a non-trivially-coalescable copy with 546 /// IntA being the source and IntB being the dest, thus this defines a value 547 /// number in IntB. If the source value number (in IntA) is defined by a 548 /// commutable instruction and its other operand is coalesced to the copy dest 549 /// register, see if we can transform the copy into a noop by commuting the 550 /// definition. For example, 551 /// 552 /// A3 = op A2 B0<kill> 553 /// ... 554 /// B1 = A3 <- this copy 555 /// ... 556 /// = op A3 <- more uses 557 /// 558 /// ==> 559 /// 560 /// B2 = op B0 A2<kill> 561 /// ... 562 /// B1 = B2 <- now an identify copy 563 /// ... 564 /// = op B2 <- more uses 565 /// 566 /// This returns true if an interval was modified. 567 /// 568 bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, 569 MachineInstr *CopyMI) { 570 assert (!CP.isPhys()); 571 572 SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 573 574 LiveInterval &IntA = 575 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 576 LiveInterval &IntB = 577 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 578 579 // BValNo is a value number in B that is defined by a copy from A. 'B1' in 580 // the example above. 581 VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx); 582 if (!BValNo || BValNo->def != CopyIdx) 583 return false; 584 585 // AValNo is the value number in A that defines the copy, A3 in the example. 586 VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true)); 587 assert(AValNo && "COPY source not live"); 588 if (AValNo->isPHIDef() || AValNo->isUnused()) 589 return false; 590 MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def); 591 if (!DefMI) 592 return false; 593 if (!DefMI->isCommutable()) 594 return false; 595 // If DefMI is a two-address instruction then commuting it will change the 596 // destination register. 597 int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg); 598 assert(DefIdx != -1); 599 unsigned UseOpIdx; 600 if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx)) 601 return false; 602 unsigned Op1, Op2, NewDstIdx; 603 if (!TII->findCommutedOpIndices(DefMI, Op1, Op2)) 604 return false; 605 if (Op1 == UseOpIdx) 606 NewDstIdx = Op2; 607 else if (Op2 == UseOpIdx) 608 NewDstIdx = Op1; 609 else 610 return false; 611 612 MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); 613 unsigned NewReg = NewDstMO.getReg(); 614 if (NewReg != IntB.reg || !IntB.Query(AValNo->def).isKill()) 615 return false; 616 617 // Make sure there are no other definitions of IntB that would reach the 618 // uses which the new definition can reach. 619 if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo)) 620 return false; 621 622 // If some of the uses of IntA.reg is already coalesced away, return false. 623 // It's not possible to determine whether it's safe to perform the coalescing. 624 for (MachineOperand &MO : MRI->use_nodbg_operands(IntA.reg)) { 625 MachineInstr *UseMI = MO.getParent(); 626 unsigned OpNo = &MO - &UseMI->getOperand(0); 627 SlotIndex UseIdx = LIS->getInstructionIndex(UseMI); 628 LiveInterval::iterator US = IntA.FindSegmentContaining(UseIdx); 629 if (US == IntA.end() || US->valno != AValNo) 630 continue; 631 // If this use is tied to a def, we can't rewrite the register. 632 if (UseMI->isRegTiedToDefOperand(OpNo)) 633 return false; 634 } 635 636 DEBUG(dbgs() << "\tremoveCopyByCommutingDef: " << AValNo->def << '\t' 637 << *DefMI); 638 639 // At this point we have decided that it is legal to do this 640 // transformation. Start by commuting the instruction. 641 MachineBasicBlock *MBB = DefMI->getParent(); 642 MachineInstr *NewMI = TII->commuteInstruction(DefMI); 643 if (!NewMI) 644 return false; 645 if (TargetRegisterInfo::isVirtualRegister(IntA.reg) && 646 TargetRegisterInfo::isVirtualRegister(IntB.reg) && 647 !MRI->constrainRegClass(IntB.reg, MRI->getRegClass(IntA.reg))) 648 return false; 649 if (NewMI != DefMI) { 650 LIS->ReplaceMachineInstrInMaps(DefMI, NewMI); 651 MachineBasicBlock::iterator Pos = DefMI; 652 MBB->insert(Pos, NewMI); 653 MBB->erase(DefMI); 654 } 655 unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false); 656 NewMI->getOperand(OpIdx).setIsKill(); 657 658 // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g. 659 // A = or A, B 660 // ... 661 // B = A 662 // ... 663 // C = A<kill> 664 // ... 665 // = B 666 667 // Update uses of IntA of the specific Val# with IntB. 668 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(IntA.reg), 669 UE = MRI->use_end(); UI != UE;) { 670 MachineOperand &UseMO = *UI; 671 MachineInstr *UseMI = UseMO.getParent(); 672 ++UI; 673 if (UseMI->isDebugValue()) { 674 // FIXME These don't have an instruction index. Not clear we have enough 675 // info to decide whether to do this replacement or not. For now do it. 676 UseMO.setReg(NewReg); 677 continue; 678 } 679 SlotIndex UseIdx = LIS->getInstructionIndex(UseMI).getRegSlot(true); 680 LiveInterval::iterator US = IntA.FindSegmentContaining(UseIdx); 681 if (US == IntA.end() || US->valno != AValNo) 682 continue; 683 // Kill flags are no longer accurate. They are recomputed after RA. 684 UseMO.setIsKill(false); 685 if (TargetRegisterInfo::isPhysicalRegister(NewReg)) 686 UseMO.substPhysReg(NewReg, *TRI); 687 else 688 UseMO.setReg(NewReg); 689 if (UseMI == CopyMI) 690 continue; 691 if (!UseMI->isCopy()) 692 continue; 693 if (UseMI->getOperand(0).getReg() != IntB.reg || 694 UseMI->getOperand(0).getSubReg()) 695 continue; 696 697 // This copy will become a noop. If it's defining a new val#, merge it into 698 // BValNo. 699 SlotIndex DefIdx = UseIdx.getRegSlot(); 700 VNInfo *DVNI = IntB.getVNInfoAt(DefIdx); 701 if (!DVNI) 702 continue; 703 DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI); 704 assert(DVNI->def == DefIdx); 705 BValNo = IntB.MergeValueNumberInto(BValNo, DVNI); 706 ErasedInstrs.insert(UseMI); 707 LIS->RemoveMachineInstrFromMaps(UseMI); 708 UseMI->eraseFromParent(); 709 } 710 711 // Extend BValNo by merging in IntA live segments of AValNo. Val# definition 712 // is updated. 713 VNInfo *ValNo = BValNo; 714 ValNo->def = AValNo->def; 715 for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 716 AI != AE; ++AI) { 717 if (AI->valno != AValNo) continue; 718 IntB.addSegment(LiveInterval::Segment(AI->start, AI->end, ValNo)); 719 } 720 DEBUG(dbgs() << "\t\textended: " << IntB << '\n'); 721 722 IntA.removeValNo(AValNo); 723 DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n'); 724 ++numCommutes; 725 return true; 726 } 727 728 /// reMaterializeTrivialDef - If the source of a copy is defined by a trivial 729 /// computation, replace the copy by rematerialize the definition. 730 bool RegisterCoalescer::reMaterializeTrivialDef(CoalescerPair &CP, 731 MachineInstr *CopyMI, 732 bool &IsDefCopy) { 733 IsDefCopy = false; 734 unsigned SrcReg = CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg(); 735 unsigned SrcIdx = CP.isFlipped() ? CP.getDstIdx() : CP.getSrcIdx(); 736 unsigned DstReg = CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg(); 737 unsigned DstIdx = CP.isFlipped() ? CP.getSrcIdx() : CP.getDstIdx(); 738 if (TargetRegisterInfo::isPhysicalRegister(SrcReg)) 739 return false; 740 741 LiveInterval &SrcInt = LIS->getInterval(SrcReg); 742 SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI); 743 VNInfo *ValNo = SrcInt.Query(CopyIdx).valueIn(); 744 assert(ValNo && "CopyMI input register not live"); 745 if (ValNo->isPHIDef() || ValNo->isUnused()) 746 return false; 747 MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def); 748 if (!DefMI) 749 return false; 750 if (DefMI->isCopyLike()) { 751 IsDefCopy = true; 752 return false; 753 } 754 if (!TII->isAsCheapAsAMove(DefMI)) 755 return false; 756 if (!TII->isTriviallyReMaterializable(DefMI, AA)) 757 return false; 758 bool SawStore = false; 759 if (!DefMI->isSafeToMove(TII, AA, SawStore)) 760 return false; 761 const MCInstrDesc &MCID = DefMI->getDesc(); 762 if (MCID.getNumDefs() != 1) 763 return false; 764 // Only support subregister destinations when the def is read-undef. 765 MachineOperand &DstOperand = CopyMI->getOperand(0); 766 unsigned CopyDstReg = DstOperand.getReg(); 767 if (DstOperand.getSubReg() && !DstOperand.isUndef()) 768 return false; 769 770 // If both SrcIdx and DstIdx are set, correct rematerialization would widen 771 // the register substantially (beyond both source and dest size). This is bad 772 // for performance since it can cascade through a function, introducing many 773 // extra spills and fills (e.g. ARM can easily end up copying QQQQPR registers 774 // around after a few subreg copies). 775 if (SrcIdx && DstIdx) 776 return false; 777 778 const TargetRegisterClass *DefRC = TII->getRegClass(MCID, 0, TRI, *MF); 779 if (!DefMI->isImplicitDef()) { 780 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { 781 unsigned NewDstReg = DstReg; 782 783 unsigned NewDstIdx = TRI->composeSubRegIndices(CP.getSrcIdx(), 784 DefMI->getOperand(0).getSubReg()); 785 if (NewDstIdx) 786 NewDstReg = TRI->getSubReg(DstReg, NewDstIdx); 787 788 // Finally, make sure that the physical subregister that will be 789 // constructed later is permitted for the instruction. 790 if (!DefRC->contains(NewDstReg)) 791 return false; 792 } else { 793 // Theoretically, some stack frame reference could exist. Just make sure 794 // it hasn't actually happened. 795 assert(TargetRegisterInfo::isVirtualRegister(DstReg) && 796 "Only expect to deal with virtual or physical registers"); 797 } 798 } 799 800 MachineBasicBlock *MBB = CopyMI->getParent(); 801 MachineBasicBlock::iterator MII = 802 std::next(MachineBasicBlock::iterator(CopyMI)); 803 TII->reMaterialize(*MBB, MII, DstReg, SrcIdx, DefMI, *TRI); 804 MachineInstr *NewMI = std::prev(MII); 805 806 LIS->ReplaceMachineInstrInMaps(CopyMI, NewMI); 807 CopyMI->eraseFromParent(); 808 ErasedInstrs.insert(CopyMI); 809 810 // NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86). 811 // We need to remember these so we can add intervals once we insert 812 // NewMI into SlotIndexes. 813 SmallVector<unsigned, 4> NewMIImplDefs; 814 for (unsigned i = NewMI->getDesc().getNumOperands(), 815 e = NewMI->getNumOperands(); i != e; ++i) { 816 MachineOperand &MO = NewMI->getOperand(i); 817 if (MO.isReg()) { 818 assert(MO.isDef() && MO.isImplicit() && MO.isDead() && 819 TargetRegisterInfo::isPhysicalRegister(MO.getReg())); 820 NewMIImplDefs.push_back(MO.getReg()); 821 } 822 } 823 824 if (TargetRegisterInfo::isVirtualRegister(DstReg)) { 825 const TargetRegisterClass *NewRC = CP.getNewRC(); 826 unsigned NewIdx = NewMI->getOperand(0).getSubReg(); 827 828 if (NewIdx) 829 NewRC = TRI->getMatchingSuperRegClass(NewRC, DefRC, NewIdx); 830 else 831 NewRC = TRI->getCommonSubClass(NewRC, DefRC); 832 833 assert(NewRC && "subreg chosen for remat incompatible with instruction"); 834 MRI->setRegClass(DstReg, NewRC); 835 836 updateRegDefsUses(DstReg, DstReg, DstIdx); 837 NewMI->getOperand(0).setSubReg(NewIdx); 838 } else if (NewMI->getOperand(0).getReg() != CopyDstReg) { 839 // The New instruction may be defining a sub-register of what's actually 840 // been asked for. If so it must implicitly define the whole thing. 841 assert(TargetRegisterInfo::isPhysicalRegister(DstReg) && 842 "Only expect virtual or physical registers in remat"); 843 NewMI->getOperand(0).setIsDead(true); 844 NewMI->addOperand(MachineOperand::CreateReg(CopyDstReg, 845 true /*IsDef*/, 846 true /*IsImp*/, 847 false /*IsKill*/)); 848 // Record small dead def live-ranges for all the subregisters 849 // of the destination register. 850 // Otherwise, variables that live through may miss some 851 // interferences, thus creating invalid allocation. 852 // E.g., i386 code: 853 // vreg1 = somedef ; vreg1 GR8 854 // vreg2 = remat ; vreg2 GR32 855 // CL = COPY vreg2.sub_8bit 856 // = somedef vreg1 ; vreg1 GR8 857 // => 858 // vreg1 = somedef ; vreg1 GR8 859 // ECX<def, dead> = remat ; CL<imp-def> 860 // = somedef vreg1 ; vreg1 GR8 861 // vreg1 will see the inteferences with CL but not with CH since 862 // no live-ranges would have been created for ECX. 863 // Fix that! 864 SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI); 865 for (MCRegUnitIterator Units(NewMI->getOperand(0).getReg(), TRI); 866 Units.isValid(); ++Units) 867 if (LiveRange *LR = LIS->getCachedRegUnit(*Units)) 868 LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator()); 869 } 870 871 if (NewMI->getOperand(0).getSubReg()) 872 NewMI->getOperand(0).setIsUndef(); 873 874 // CopyMI may have implicit operands, transfer them over to the newly 875 // rematerialized instruction. And update implicit def interval valnos. 876 for (unsigned i = CopyMI->getDesc().getNumOperands(), 877 e = CopyMI->getNumOperands(); i != e; ++i) { 878 MachineOperand &MO = CopyMI->getOperand(i); 879 if (MO.isReg()) { 880 assert(MO.isImplicit() && "No explicit operands after implict operands."); 881 // Discard VReg implicit defs. 882 if (TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { 883 NewMI->addOperand(MO); 884 } 885 } 886 } 887 888 SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI); 889 for (unsigned i = 0, e = NewMIImplDefs.size(); i != e; ++i) { 890 unsigned Reg = NewMIImplDefs[i]; 891 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) 892 if (LiveRange *LR = LIS->getCachedRegUnit(*Units)) 893 LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator()); 894 } 895 896 DEBUG(dbgs() << "Remat: " << *NewMI); 897 ++NumReMats; 898 899 // The source interval can become smaller because we removed a use. 900 LIS->shrinkToUses(&SrcInt, &DeadDefs); 901 if (!DeadDefs.empty()) 902 eliminateDeadDefs(); 903 904 return true; 905 } 906 907 /// eliminateUndefCopy - ProcessImpicitDefs may leave some copies of <undef> 908 /// values, it only removes local variables. When we have a copy like: 909 /// 910 /// %vreg1 = COPY %vreg2<undef> 911 /// 912 /// We delete the copy and remove the corresponding value number from %vreg1. 913 /// Any uses of that value number are marked as <undef>. 914 bool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI, 915 const CoalescerPair &CP) { 916 SlotIndex Idx = LIS->getInstructionIndex(CopyMI); 917 LiveInterval *SrcInt = &LIS->getInterval(CP.getSrcReg()); 918 if (SrcInt->liveAt(Idx)) 919 return false; 920 LiveInterval *DstInt = &LIS->getInterval(CP.getDstReg()); 921 if (DstInt->liveAt(Idx)) 922 return false; 923 924 // No intervals are live-in to CopyMI - it is undef. 925 if (CP.isFlipped()) 926 DstInt = SrcInt; 927 SrcInt = nullptr; 928 929 VNInfo *DeadVNI = DstInt->getVNInfoAt(Idx.getRegSlot()); 930 assert(DeadVNI && "No value defined in DstInt"); 931 DstInt->removeValNo(DeadVNI); 932 933 // Find new undef uses. 934 for (MachineOperand &MO : MRI->reg_nodbg_operands(DstInt->reg)) { 935 if (MO.isDef() || MO.isUndef()) 936 continue; 937 MachineInstr *MI = MO.getParent(); 938 SlotIndex Idx = LIS->getInstructionIndex(MI); 939 if (DstInt->liveAt(Idx)) 940 continue; 941 MO.setIsUndef(true); 942 DEBUG(dbgs() << "\tnew undef: " << Idx << '\t' << *MI); 943 } 944 return true; 945 } 946 947 /// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 948 /// update the subregister number if it is not zero. If DstReg is a 949 /// physical register and the existing subregister number of the def / use 950 /// being updated is not zero, make sure to set it to the correct physical 951 /// subregister. 952 void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg, 953 unsigned DstReg, 954 unsigned SubIdx) { 955 bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 956 LiveInterval *DstInt = DstIsPhys ? nullptr : &LIS->getInterval(DstReg); 957 958 SmallPtrSet<MachineInstr*, 8> Visited; 959 for (MachineRegisterInfo::reg_instr_iterator 960 I = MRI->reg_instr_begin(SrcReg), E = MRI->reg_instr_end(); 961 I != E; ) { 962 MachineInstr *UseMI = &*(I++); 963 964 // Each instruction can only be rewritten once because sub-register 965 // composition is not always idempotent. When SrcReg != DstReg, rewriting 966 // the UseMI operands removes them from the SrcReg use-def chain, but when 967 // SrcReg is DstReg we could encounter UseMI twice if it has multiple 968 // operands mentioning the virtual register. 969 if (SrcReg == DstReg && !Visited.insert(UseMI)) 970 continue; 971 972 SmallVector<unsigned,8> Ops; 973 bool Reads, Writes; 974 std::tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops); 975 976 // If SrcReg wasn't read, it may still be the case that DstReg is live-in 977 // because SrcReg is a sub-register. 978 if (DstInt && !Reads && SubIdx) 979 Reads = DstInt->liveAt(LIS->getInstructionIndex(UseMI)); 980 981 // Replace SrcReg with DstReg in all UseMI operands. 982 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 983 MachineOperand &MO = UseMI->getOperand(Ops[i]); 984 985 // Adjust <undef> flags in case of sub-register joins. We don't want to 986 // turn a full def into a read-modify-write sub-register def and vice 987 // versa. 988 if (SubIdx && MO.isDef()) 989 MO.setIsUndef(!Reads); 990 991 if (DstIsPhys) 992 MO.substPhysReg(DstReg, *TRI); 993 else 994 MO.substVirtReg(DstReg, SubIdx, *TRI); 995 } 996 997 DEBUG({ 998 dbgs() << "\t\tupdated: "; 999 if (!UseMI->isDebugValue()) 1000 dbgs() << LIS->getInstructionIndex(UseMI) << "\t"; 1001 dbgs() << *UseMI; 1002 }); 1003 } 1004 } 1005 1006 /// canJoinPhys - Return true if a copy involving a physreg should be joined. 1007 bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) { 1008 /// Always join simple intervals that are defined by a single copy from a 1009 /// reserved register. This doesn't increase register pressure, so it is 1010 /// always beneficial. 1011 if (!MRI->isReserved(CP.getDstReg())) { 1012 DEBUG(dbgs() << "\tCan only merge into reserved registers.\n"); 1013 return false; 1014 } 1015 1016 LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg()); 1017 if (CP.isFlipped() && JoinVInt.containsOneValue()) 1018 return true; 1019 1020 DEBUG(dbgs() << "\tCannot join defs into reserved register.\n"); 1021 return false; 1022 } 1023 1024 /// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 1025 /// which are the src/dst of the copy instruction CopyMI. This returns true 1026 /// if the copy was successfully coalesced away. If it is not currently 1027 /// possible to coalesce this interval, but it may be possible if other 1028 /// things get coalesced, then it returns true by reference in 'Again'. 1029 bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { 1030 1031 Again = false; 1032 DEBUG(dbgs() << LIS->getInstructionIndex(CopyMI) << '\t' << *CopyMI); 1033 1034 CoalescerPair CP(*TRI); 1035 if (!CP.setRegisters(CopyMI)) { 1036 DEBUG(dbgs() << "\tNot coalescable.\n"); 1037 return false; 1038 } 1039 1040 // Dead code elimination. This really should be handled by MachineDCE, but 1041 // sometimes dead copies slip through, and we can't generate invalid live 1042 // ranges. 1043 if (!CP.isPhys() && CopyMI->allDefsAreDead()) { 1044 DEBUG(dbgs() << "\tCopy is dead.\n"); 1045 DeadDefs.push_back(CopyMI); 1046 eliminateDeadDefs(); 1047 return true; 1048 } 1049 1050 // Eliminate undefs. 1051 if (!CP.isPhys() && eliminateUndefCopy(CopyMI, CP)) { 1052 DEBUG(dbgs() << "\tEliminated copy of <undef> value.\n"); 1053 LIS->RemoveMachineInstrFromMaps(CopyMI); 1054 CopyMI->eraseFromParent(); 1055 return false; // Not coalescable. 1056 } 1057 1058 // Coalesced copies are normally removed immediately, but transformations 1059 // like removeCopyByCommutingDef() can inadvertently create identity copies. 1060 // When that happens, just join the values and remove the copy. 1061 if (CP.getSrcReg() == CP.getDstReg()) { 1062 LiveInterval &LI = LIS->getInterval(CP.getSrcReg()); 1063 DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n'); 1064 LiveQueryResult LRQ = LI.Query(LIS->getInstructionIndex(CopyMI)); 1065 if (VNInfo *DefVNI = LRQ.valueDefined()) { 1066 VNInfo *ReadVNI = LRQ.valueIn(); 1067 assert(ReadVNI && "No value before copy and no <undef> flag."); 1068 assert(ReadVNI != DefVNI && "Cannot read and define the same value."); 1069 LI.MergeValueNumberInto(DefVNI, ReadVNI); 1070 DEBUG(dbgs() << "\tMerged values: " << LI << '\n'); 1071 } 1072 LIS->RemoveMachineInstrFromMaps(CopyMI); 1073 CopyMI->eraseFromParent(); 1074 return true; 1075 } 1076 1077 // Enforce policies. 1078 if (CP.isPhys()) { 1079 DEBUG(dbgs() << "\tConsidering merging " << PrintReg(CP.getSrcReg(), TRI) 1080 << " with " << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) 1081 << '\n'); 1082 if (!canJoinPhys(CP)) { 1083 // Before giving up coalescing, if definition of source is defined by 1084 // trivial computation, try rematerializing it. 1085 bool IsDefCopy; 1086 if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy)) 1087 return true; 1088 if (IsDefCopy) 1089 Again = true; // May be possible to coalesce later. 1090 return false; 1091 } 1092 } else { 1093 DEBUG({ 1094 dbgs() << "\tConsidering merging to " << CP.getNewRC()->getName() 1095 << " with "; 1096 if (CP.getDstIdx() && CP.getSrcIdx()) 1097 dbgs() << PrintReg(CP.getDstReg()) << " in " 1098 << TRI->getSubRegIndexName(CP.getDstIdx()) << " and " 1099 << PrintReg(CP.getSrcReg()) << " in " 1100 << TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n'; 1101 else 1102 dbgs() << PrintReg(CP.getSrcReg(), TRI) << " in " 1103 << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n'; 1104 }); 1105 1106 // When possible, let DstReg be the larger interval. 1107 if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).size() > 1108 LIS->getInterval(CP.getDstReg()).size()) 1109 CP.flip(); 1110 } 1111 1112 // Okay, attempt to join these two intervals. On failure, this returns false. 1113 // Otherwise, if one of the intervals being joined is a physreg, this method 1114 // always canonicalizes DstInt to be it. The output "SrcInt" will not have 1115 // been modified, so we can use this information below to update aliases. 1116 if (!joinIntervals(CP)) { 1117 // Coalescing failed. 1118 1119 // If definition of source is defined by trivial computation, try 1120 // rematerializing it. 1121 bool IsDefCopy; 1122 if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy)) 1123 return true; 1124 1125 // If we can eliminate the copy without merging the live segments, do so 1126 // now. 1127 if (!CP.isPartial() && !CP.isPhys()) { 1128 if (adjustCopiesBackFrom(CP, CopyMI) || 1129 removeCopyByCommutingDef(CP, CopyMI)) { 1130 LIS->RemoveMachineInstrFromMaps(CopyMI); 1131 CopyMI->eraseFromParent(); 1132 DEBUG(dbgs() << "\tTrivial!\n"); 1133 return true; 1134 } 1135 } 1136 1137 // Otherwise, we are unable to join the intervals. 1138 DEBUG(dbgs() << "\tInterference!\n"); 1139 Again = true; // May be possible to coalesce later. 1140 return false; 1141 } 1142 1143 // Coalescing to a virtual register that is of a sub-register class of the 1144 // other. Make sure the resulting register is set to the right register class. 1145 if (CP.isCrossClass()) { 1146 ++numCrossRCs; 1147 MRI->setRegClass(CP.getDstReg(), CP.getNewRC()); 1148 } 1149 1150 // Removing sub-register copies can ease the register class constraints. 1151 // Make sure we attempt to inflate the register class of DstReg. 1152 if (!CP.isPhys() && RegClassInfo.isProperSubClass(CP.getNewRC())) 1153 InflateRegs.push_back(CP.getDstReg()); 1154 1155 // CopyMI has been erased by joinIntervals at this point. Remove it from 1156 // ErasedInstrs since copyCoalesceWorkList() won't add a successful join back 1157 // to the work list. This keeps ErasedInstrs from growing needlessly. 1158 ErasedInstrs.erase(CopyMI); 1159 1160 // Rewrite all SrcReg operands to DstReg. 1161 // Also update DstReg operands to include DstIdx if it is set. 1162 if (CP.getDstIdx()) 1163 updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx()); 1164 updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx()); 1165 1166 // SrcReg is guaranteed to be the register whose live interval that is 1167 // being merged. 1168 LIS->removeInterval(CP.getSrcReg()); 1169 1170 // Update regalloc hint. 1171 TRI->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF); 1172 1173 DEBUG({ 1174 dbgs() << "\tJoined. Result = "; 1175 if (CP.isPhys()) 1176 dbgs() << PrintReg(CP.getDstReg(), TRI); 1177 else 1178 dbgs() << LIS->getInterval(CP.getDstReg()); 1179 dbgs() << '\n'; 1180 }); 1181 1182 ++numJoins; 1183 return true; 1184 } 1185 1186 /// Attempt joining with a reserved physreg. 1187 bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) { 1188 assert(CP.isPhys() && "Must be a physreg copy"); 1189 assert(MRI->isReserved(CP.getDstReg()) && "Not a reserved register"); 1190 LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1191 DEBUG(dbgs() << "\t\tRHS = " << RHS << '\n'); 1192 1193 assert(CP.isFlipped() && RHS.containsOneValue() && 1194 "Invalid join with reserved register"); 1195 1196 // Optimization for reserved registers like ESP. We can only merge with a 1197 // reserved physreg if RHS has a single value that is a copy of CP.DstReg(). 1198 // The live range of the reserved register will look like a set of dead defs 1199 // - we don't properly track the live range of reserved registers. 1200 1201 // Deny any overlapping intervals. This depends on all the reserved 1202 // register live ranges to look like dead defs. 1203 for (MCRegUnitIterator UI(CP.getDstReg(), TRI); UI.isValid(); ++UI) 1204 if (RHS.overlaps(LIS->getRegUnit(*UI))) { 1205 DEBUG(dbgs() << "\t\tInterference: " << PrintRegUnit(*UI, TRI) << '\n'); 1206 return false; 1207 } 1208 1209 // Skip any value computations, we are not adding new values to the 1210 // reserved register. Also skip merging the live ranges, the reserved 1211 // register live range doesn't need to be accurate as long as all the 1212 // defs are there. 1213 1214 // Delete the identity copy. 1215 MachineInstr *CopyMI = MRI->getVRegDef(RHS.reg); 1216 LIS->RemoveMachineInstrFromMaps(CopyMI); 1217 CopyMI->eraseFromParent(); 1218 1219 // We don't track kills for reserved registers. 1220 MRI->clearKillFlags(CP.getSrcReg()); 1221 1222 return true; 1223 } 1224 1225 //===----------------------------------------------------------------------===// 1226 // Interference checking and interval joining 1227 //===----------------------------------------------------------------------===// 1228 // 1229 // In the easiest case, the two live ranges being joined are disjoint, and 1230 // there is no interference to consider. It is quite common, though, to have 1231 // overlapping live ranges, and we need to check if the interference can be 1232 // resolved. 1233 // 1234 // The live range of a single SSA value forms a sub-tree of the dominator tree. 1235 // This means that two SSA values overlap if and only if the def of one value 1236 // is contained in the live range of the other value. As a special case, the 1237 // overlapping values can be defined at the same index. 1238 // 1239 // The interference from an overlapping def can be resolved in these cases: 1240 // 1241 // 1. Coalescable copies. The value is defined by a copy that would become an 1242 // identity copy after joining SrcReg and DstReg. The copy instruction will 1243 // be removed, and the value will be merged with the source value. 1244 // 1245 // There can be several copies back and forth, causing many values to be 1246 // merged into one. We compute a list of ultimate values in the joined live 1247 // range as well as a mappings from the old value numbers. 1248 // 1249 // 2. IMPLICIT_DEF. This instruction is only inserted to ensure all PHI 1250 // predecessors have a live out value. It doesn't cause real interference, 1251 // and can be merged into the value it overlaps. Like a coalescable copy, it 1252 // can be erased after joining. 1253 // 1254 // 3. Copy of external value. The overlapping def may be a copy of a value that 1255 // is already in the other register. This is like a coalescable copy, but 1256 // the live range of the source register must be trimmed after erasing the 1257 // copy instruction: 1258 // 1259 // %src = COPY %ext 1260 // %dst = COPY %ext <-- Remove this COPY, trim the live range of %ext. 1261 // 1262 // 4. Clobbering undefined lanes. Vector registers are sometimes built by 1263 // defining one lane at a time: 1264 // 1265 // %dst:ssub0<def,read-undef> = FOO 1266 // %src = BAR 1267 // %dst:ssub1<def> = COPY %src 1268 // 1269 // The live range of %src overlaps the %dst value defined by FOO, but 1270 // merging %src into %dst:ssub1 is only going to clobber the ssub1 lane 1271 // which was undef anyway. 1272 // 1273 // The value mapping is more complicated in this case. The final live range 1274 // will have different value numbers for both FOO and BAR, but there is no 1275 // simple mapping from old to new values. It may even be necessary to add 1276 // new PHI values. 1277 // 1278 // 5. Clobbering dead lanes. A def may clobber a lane of a vector register that 1279 // is live, but never read. This can happen because we don't compute 1280 // individual live ranges per lane. 1281 // 1282 // %dst<def> = FOO 1283 // %src = BAR 1284 // %dst:ssub1<def> = COPY %src 1285 // 1286 // This kind of interference is only resolved locally. If the clobbered 1287 // lane value escapes the block, the join is aborted. 1288 1289 namespace { 1290 /// Track information about values in a single virtual register about to be 1291 /// joined. Objects of this class are always created in pairs - one for each 1292 /// side of the CoalescerPair. 1293 class JoinVals { 1294 LiveInterval &LI; 1295 1296 // Location of this register in the final joined register. 1297 // Either CP.DstIdx or CP.SrcIdx. 1298 unsigned SubIdx; 1299 1300 // Values that will be present in the final live range. 1301 SmallVectorImpl<VNInfo*> &NewVNInfo; 1302 1303 const CoalescerPair &CP; 1304 LiveIntervals *LIS; 1305 SlotIndexes *Indexes; 1306 const TargetRegisterInfo *TRI; 1307 1308 // Value number assignments. Maps value numbers in LI to entries in NewVNInfo. 1309 // This is suitable for passing to LiveInterval::join(). 1310 SmallVector<int, 8> Assignments; 1311 1312 // Conflict resolution for overlapping values. 1313 enum ConflictResolution { 1314 // No overlap, simply keep this value. 1315 CR_Keep, 1316 1317 // Merge this value into OtherVNI and erase the defining instruction. 1318 // Used for IMPLICIT_DEF, coalescable copies, and copies from external 1319 // values. 1320 CR_Erase, 1321 1322 // Merge this value into OtherVNI but keep the defining instruction. 1323 // This is for the special case where OtherVNI is defined by the same 1324 // instruction. 1325 CR_Merge, 1326 1327 // Keep this value, and have it replace OtherVNI where possible. This 1328 // complicates value mapping since OtherVNI maps to two different values 1329 // before and after this def. 1330 // Used when clobbering undefined or dead lanes. 1331 CR_Replace, 1332 1333 // Unresolved conflict. Visit later when all values have been mapped. 1334 CR_Unresolved, 1335 1336 // Unresolvable conflict. Abort the join. 1337 CR_Impossible 1338 }; 1339 1340 // Per-value info for LI. The lane bit masks are all relative to the final 1341 // joined register, so they can be compared directly between SrcReg and 1342 // DstReg. 1343 struct Val { 1344 ConflictResolution Resolution; 1345 1346 // Lanes written by this def, 0 for unanalyzed values. 1347 unsigned WriteLanes; 1348 1349 // Lanes with defined values in this register. Other lanes are undef and 1350 // safe to clobber. 1351 unsigned ValidLanes; 1352 1353 // Value in LI being redefined by this def. 1354 VNInfo *RedefVNI; 1355 1356 // Value in the other live range that overlaps this def, if any. 1357 VNInfo *OtherVNI; 1358 1359 // Is this value an IMPLICIT_DEF that can be erased? 1360 // 1361 // IMPLICIT_DEF values should only exist at the end of a basic block that 1362 // is a predecessor to a phi-value. These IMPLICIT_DEF instructions can be 1363 // safely erased if they are overlapping a live value in the other live 1364 // interval. 1365 // 1366 // Weird control flow graphs and incomplete PHI handling in 1367 // ProcessImplicitDefs can very rarely create IMPLICIT_DEF values with 1368 // longer live ranges. Such IMPLICIT_DEF values should be treated like 1369 // normal values. 1370 bool ErasableImplicitDef; 1371 1372 // True when the live range of this value will be pruned because of an 1373 // overlapping CR_Replace value in the other live range. 1374 bool Pruned; 1375 1376 // True once Pruned above has been computed. 1377 bool PrunedComputed; 1378 1379 Val() : Resolution(CR_Keep), WriteLanes(0), ValidLanes(0), 1380 RedefVNI(nullptr), OtherVNI(nullptr), ErasableImplicitDef(false), 1381 Pruned(false), PrunedComputed(false) {} 1382 1383 bool isAnalyzed() const { return WriteLanes != 0; } 1384 }; 1385 1386 // One entry per value number in LI. 1387 SmallVector<Val, 8> Vals; 1388 1389 unsigned computeWriteLanes(const MachineInstr *DefMI, bool &Redef); 1390 VNInfo *stripCopies(VNInfo *VNI); 1391 ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other); 1392 void computeAssignment(unsigned ValNo, JoinVals &Other); 1393 bool taintExtent(unsigned, unsigned, JoinVals&, 1394 SmallVectorImpl<std::pair<SlotIndex, unsigned> >&); 1395 bool usesLanes(MachineInstr *MI, unsigned, unsigned, unsigned); 1396 bool isPrunedValue(unsigned ValNo, JoinVals &Other); 1397 1398 public: 1399 JoinVals(LiveInterval &li, unsigned subIdx, 1400 SmallVectorImpl<VNInfo*> &newVNInfo, 1401 const CoalescerPair &cp, 1402 LiveIntervals *lis, 1403 const TargetRegisterInfo *tri) 1404 : LI(li), SubIdx(subIdx), NewVNInfo(newVNInfo), CP(cp), LIS(lis), 1405 Indexes(LIS->getSlotIndexes()), TRI(tri), 1406 Assignments(LI.getNumValNums(), -1), Vals(LI.getNumValNums()) 1407 {} 1408 1409 /// Analyze defs in LI and compute a value mapping in NewVNInfo. 1410 /// Returns false if any conflicts were impossible to resolve. 1411 bool mapValues(JoinVals &Other); 1412 1413 /// Try to resolve conflicts that require all values to be mapped. 1414 /// Returns false if any conflicts were impossible to resolve. 1415 bool resolveConflicts(JoinVals &Other); 1416 1417 /// Prune the live range of values in Other.LI where they would conflict with 1418 /// CR_Replace values in LI. Collect end points for restoring the live range 1419 /// after joining. 1420 void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints); 1421 1422 /// Erase any machine instructions that have been coalesced away. 1423 /// Add erased instructions to ErasedInstrs. 1424 /// Add foreign virtual registers to ShrinkRegs if their live range ended at 1425 /// the erased instrs. 1426 void eraseInstrs(SmallPtrSet<MachineInstr*, 8> &ErasedInstrs, 1427 SmallVectorImpl<unsigned> &ShrinkRegs); 1428 1429 /// Get the value assignments suitable for passing to LiveInterval::join. 1430 const int *getAssignments() const { return Assignments.data(); } 1431 }; 1432 } // end anonymous namespace 1433 1434 /// Compute the bitmask of lanes actually written by DefMI. 1435 /// Set Redef if there are any partial register definitions that depend on the 1436 /// previous value of the register. 1437 unsigned JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef) { 1438 unsigned L = 0; 1439 for (ConstMIOperands MO(DefMI); MO.isValid(); ++MO) { 1440 if (!MO->isReg() || MO->getReg() != LI.reg || !MO->isDef()) 1441 continue; 1442 L |= TRI->getSubRegIndexLaneMask( 1443 TRI->composeSubRegIndices(SubIdx, MO->getSubReg())); 1444 if (MO->readsReg()) 1445 Redef = true; 1446 } 1447 return L; 1448 } 1449 1450 /// Find the ultimate value that VNI was copied from. 1451 VNInfo *JoinVals::stripCopies(VNInfo *VNI) { 1452 while (!VNI->isPHIDef()) { 1453 MachineInstr *MI = Indexes->getInstructionFromIndex(VNI->def); 1454 assert(MI && "No defining instruction"); 1455 if (!MI->isFullCopy()) 1456 break; 1457 unsigned Reg = MI->getOperand(1).getReg(); 1458 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1459 break; 1460 LiveQueryResult LRQ = LIS->getInterval(Reg).Query(VNI->def); 1461 if (!LRQ.valueIn()) 1462 break; 1463 VNI = LRQ.valueIn(); 1464 } 1465 return VNI; 1466 } 1467 1468 /// Analyze ValNo in this live range, and set all fields of Vals[ValNo]. 1469 /// Return a conflict resolution when possible, but leave the hard cases as 1470 /// CR_Unresolved. 1471 /// Recursively calls computeAssignment() on this and Other, guaranteeing that 1472 /// both OtherVNI and RedefVNI have been analyzed and mapped before returning. 1473 /// The recursion always goes upwards in the dominator tree, making loops 1474 /// impossible. 1475 JoinVals::ConflictResolution 1476 JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) { 1477 Val &V = Vals[ValNo]; 1478 assert(!V.isAnalyzed() && "Value has already been analyzed!"); 1479 VNInfo *VNI = LI.getValNumInfo(ValNo); 1480 if (VNI->isUnused()) { 1481 V.WriteLanes = ~0u; 1482 return CR_Keep; 1483 } 1484 1485 // Get the instruction defining this value, compute the lanes written. 1486 const MachineInstr *DefMI = nullptr; 1487 if (VNI->isPHIDef()) { 1488 // Conservatively assume that all lanes in a PHI are valid. 1489 V.ValidLanes = V.WriteLanes = TRI->getSubRegIndexLaneMask(SubIdx); 1490 } else { 1491 DefMI = Indexes->getInstructionFromIndex(VNI->def); 1492 bool Redef = false; 1493 V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef); 1494 1495 // If this is a read-modify-write instruction, there may be more valid 1496 // lanes than the ones written by this instruction. 1497 // This only covers partial redef operands. DefMI may have normal use 1498 // operands reading the register. They don't contribute valid lanes. 1499 // 1500 // This adds ssub1 to the set of valid lanes in %src: 1501 // 1502 // %src:ssub1<def> = FOO 1503 // 1504 // This leaves only ssub1 valid, making any other lanes undef: 1505 // 1506 // %src:ssub1<def,read-undef> = FOO %src:ssub2 1507 // 1508 // The <read-undef> flag on the def operand means that old lane values are 1509 // not important. 1510 if (Redef) { 1511 V.RedefVNI = LI.Query(VNI->def).valueIn(); 1512 assert(V.RedefVNI && "Instruction is reading nonexistent value"); 1513 computeAssignment(V.RedefVNI->id, Other); 1514 V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes; 1515 } 1516 1517 // An IMPLICIT_DEF writes undef values. 1518 if (DefMI->isImplicitDef()) { 1519 // We normally expect IMPLICIT_DEF values to be live only until the end 1520 // of their block. If the value is really live longer and gets pruned in 1521 // another block, this flag is cleared again. 1522 V.ErasableImplicitDef = true; 1523 V.ValidLanes &= ~V.WriteLanes; 1524 } 1525 } 1526 1527 // Find the value in Other that overlaps VNI->def, if any. 1528 LiveQueryResult OtherLRQ = Other.LI.Query(VNI->def); 1529 1530 // It is possible that both values are defined by the same instruction, or 1531 // the values are PHIs defined in the same block. When that happens, the two 1532 // values should be merged into one, but not into any preceding value. 1533 // The first value defined or visited gets CR_Keep, the other gets CR_Merge. 1534 if (VNInfo *OtherVNI = OtherLRQ.valueDefined()) { 1535 assert(SlotIndex::isSameInstr(VNI->def, OtherVNI->def) && "Broken LRQ"); 1536 1537 // One value stays, the other is merged. Keep the earlier one, or the first 1538 // one we see. 1539 if (OtherVNI->def < VNI->def) 1540 Other.computeAssignment(OtherVNI->id, *this); 1541 else if (VNI->def < OtherVNI->def && OtherLRQ.valueIn()) { 1542 // This is an early-clobber def overlapping a live-in value in the other 1543 // register. Not mergeable. 1544 V.OtherVNI = OtherLRQ.valueIn(); 1545 return CR_Impossible; 1546 } 1547 V.OtherVNI = OtherVNI; 1548 Val &OtherV = Other.Vals[OtherVNI->id]; 1549 // Keep this value, check for conflicts when analyzing OtherVNI. 1550 if (!OtherV.isAnalyzed()) 1551 return CR_Keep; 1552 // Both sides have been analyzed now. 1553 // Allow overlapping PHI values. Any real interference would show up in a 1554 // predecessor, the PHI itself can't introduce any conflicts. 1555 if (VNI->isPHIDef()) 1556 return CR_Merge; 1557 if (V.ValidLanes & OtherV.ValidLanes) 1558 // Overlapping lanes can't be resolved. 1559 return CR_Impossible; 1560 else 1561 return CR_Merge; 1562 } 1563 1564 // No simultaneous def. Is Other live at the def? 1565 V.OtherVNI = OtherLRQ.valueIn(); 1566 if (!V.OtherVNI) 1567 // No overlap, no conflict. 1568 return CR_Keep; 1569 1570 assert(!SlotIndex::isSameInstr(VNI->def, V.OtherVNI->def) && "Broken LRQ"); 1571 1572 // We have overlapping values, or possibly a kill of Other. 1573 // Recursively compute assignments up the dominator tree. 1574 Other.computeAssignment(V.OtherVNI->id, *this); 1575 Val &OtherV = Other.Vals[V.OtherVNI->id]; 1576 1577 // Check if OtherV is an IMPLICIT_DEF that extends beyond its basic block. 1578 // This shouldn't normally happen, but ProcessImplicitDefs can leave such 1579 // IMPLICIT_DEF instructions behind, and there is nothing wrong with it 1580 // technically. 1581 // 1582 // WHen it happens, treat that IMPLICIT_DEF as a normal value, and don't try 1583 // to erase the IMPLICIT_DEF instruction. 1584 if (OtherV.ErasableImplicitDef && DefMI && 1585 DefMI->getParent() != Indexes->getMBBFromIndex(V.OtherVNI->def)) { 1586 DEBUG(dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def 1587 << " extends into BB#" << DefMI->getParent()->getNumber() 1588 << ", keeping it.\n"); 1589 OtherV.ErasableImplicitDef = false; 1590 } 1591 1592 // Allow overlapping PHI values. Any real interference would show up in a 1593 // predecessor, the PHI itself can't introduce any conflicts. 1594 if (VNI->isPHIDef()) 1595 return CR_Replace; 1596 1597 // Check for simple erasable conflicts. 1598 if (DefMI->isImplicitDef()) 1599 return CR_Erase; 1600 1601 // Include the non-conflict where DefMI is a coalescable copy that kills 1602 // OtherVNI. We still want the copy erased and value numbers merged. 1603 if (CP.isCoalescable(DefMI)) { 1604 // Some of the lanes copied from OtherVNI may be undef, making them undef 1605 // here too. 1606 V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes; 1607 return CR_Erase; 1608 } 1609 1610 // This may not be a real conflict if DefMI simply kills Other and defines 1611 // VNI. 1612 if (OtherLRQ.isKill() && OtherLRQ.endPoint() <= VNI->def) 1613 return CR_Keep; 1614 1615 // Handle the case where VNI and OtherVNI can be proven to be identical: 1616 // 1617 // %other = COPY %ext 1618 // %this = COPY %ext <-- Erase this copy 1619 // 1620 if (DefMI->isFullCopy() && !CP.isPartial() && 1621 stripCopies(VNI) == stripCopies(V.OtherVNI)) 1622 return CR_Erase; 1623 1624 // If the lanes written by this instruction were all undef in OtherVNI, it is 1625 // still safe to join the live ranges. This can't be done with a simple value 1626 // mapping, though - OtherVNI will map to multiple values: 1627 // 1628 // 1 %dst:ssub0 = FOO <-- OtherVNI 1629 // 2 %src = BAR <-- VNI 1630 // 3 %dst:ssub1 = COPY %src<kill> <-- Eliminate this copy. 1631 // 4 BAZ %dst<kill> 1632 // 5 QUUX %src<kill> 1633 // 1634 // Here OtherVNI will map to itself in [1;2), but to VNI in [2;5). CR_Replace 1635 // handles this complex value mapping. 1636 if ((V.WriteLanes & OtherV.ValidLanes) == 0) 1637 return CR_Replace; 1638 1639 // If the other live range is killed by DefMI and the live ranges are still 1640 // overlapping, it must be because we're looking at an early clobber def: 1641 // 1642 // %dst<def,early-clobber> = ASM %src<kill> 1643 // 1644 // In this case, it is illegal to merge the two live ranges since the early 1645 // clobber def would clobber %src before it was read. 1646 if (OtherLRQ.isKill()) { 1647 // This case where the def doesn't overlap the kill is handled above. 1648 assert(VNI->def.isEarlyClobber() && 1649 "Only early clobber defs can overlap a kill"); 1650 return CR_Impossible; 1651 } 1652 1653 // VNI is clobbering live lanes in OtherVNI, but there is still the 1654 // possibility that no instructions actually read the clobbered lanes. 1655 // If we're clobbering all the lanes in OtherVNI, at least one must be read. 1656 // Otherwise Other.LI wouldn't be live here. 1657 if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes) == 0) 1658 return CR_Impossible; 1659 1660 // We need to verify that no instructions are reading the clobbered lanes. To 1661 // save compile time, we'll only check that locally. Don't allow the tainted 1662 // value to escape the basic block. 1663 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1664 if (OtherLRQ.endPoint() >= Indexes->getMBBEndIdx(MBB)) 1665 return CR_Impossible; 1666 1667 // There are still some things that could go wrong besides clobbered lanes 1668 // being read, for example OtherVNI may be only partially redefined in MBB, 1669 // and some clobbered lanes could escape the block. Save this analysis for 1670 // resolveConflicts() when all values have been mapped. We need to know 1671 // RedefVNI and WriteLanes for any later defs in MBB, and we can't compute 1672 // that now - the recursive analyzeValue() calls must go upwards in the 1673 // dominator tree. 1674 return CR_Unresolved; 1675 } 1676 1677 /// Compute the value assignment for ValNo in LI. 1678 /// This may be called recursively by analyzeValue(), but never for a ValNo on 1679 /// the stack. 1680 void JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) { 1681 Val &V = Vals[ValNo]; 1682 if (V.isAnalyzed()) { 1683 // Recursion should always move up the dominator tree, so ValNo is not 1684 // supposed to reappear before it has been assigned. 1685 assert(Assignments[ValNo] != -1 && "Bad recursion?"); 1686 return; 1687 } 1688 switch ((V.Resolution = analyzeValue(ValNo, Other))) { 1689 case CR_Erase: 1690 case CR_Merge: 1691 // Merge this ValNo into OtherVNI. 1692 assert(V.OtherVNI && "OtherVNI not assigned, can't merge."); 1693 assert(Other.Vals[V.OtherVNI->id].isAnalyzed() && "Missing recursion"); 1694 Assignments[ValNo] = Other.Assignments[V.OtherVNI->id]; 1695 DEBUG(dbgs() << "\t\tmerge " << PrintReg(LI.reg) << ':' << ValNo << '@' 1696 << LI.getValNumInfo(ValNo)->def << " into " 1697 << PrintReg(Other.LI.reg) << ':' << V.OtherVNI->id << '@' 1698 << V.OtherVNI->def << " --> @" 1699 << NewVNInfo[Assignments[ValNo]]->def << '\n'); 1700 break; 1701 case CR_Replace: 1702 case CR_Unresolved: 1703 // The other value is going to be pruned if this join is successful. 1704 assert(V.OtherVNI && "OtherVNI not assigned, can't prune"); 1705 Other.Vals[V.OtherVNI->id].Pruned = true; 1706 // Fall through. 1707 default: 1708 // This value number needs to go in the final joined live range. 1709 Assignments[ValNo] = NewVNInfo.size(); 1710 NewVNInfo.push_back(LI.getValNumInfo(ValNo)); 1711 break; 1712 } 1713 } 1714 1715 bool JoinVals::mapValues(JoinVals &Other) { 1716 for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1717 computeAssignment(i, Other); 1718 if (Vals[i].Resolution == CR_Impossible) { 1719 DEBUG(dbgs() << "\t\tinterference at " << PrintReg(LI.reg) << ':' << i 1720 << '@' << LI.getValNumInfo(i)->def << '\n'); 1721 return false; 1722 } 1723 } 1724 return true; 1725 } 1726 1727 /// Assuming ValNo is going to clobber some valid lanes in Other.LI, compute 1728 /// the extent of the tainted lanes in the block. 1729 /// 1730 /// Multiple values in Other.LI can be affected since partial redefinitions can 1731 /// preserve previously tainted lanes. 1732 /// 1733 /// 1 %dst = VLOAD <-- Define all lanes in %dst 1734 /// 2 %src = FOO <-- ValNo to be joined with %dst:ssub0 1735 /// 3 %dst:ssub1 = BAR <-- Partial redef doesn't clear taint in ssub0 1736 /// 4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read 1737 /// 1738 /// For each ValNo in Other that is affected, add an (EndIndex, TaintedLanes) 1739 /// entry to TaintedVals. 1740 /// 1741 /// Returns false if the tainted lanes extend beyond the basic block. 1742 bool JoinVals:: 1743 taintExtent(unsigned ValNo, unsigned TaintedLanes, JoinVals &Other, 1744 SmallVectorImpl<std::pair<SlotIndex, unsigned> > &TaintExtent) { 1745 VNInfo *VNI = LI.getValNumInfo(ValNo); 1746 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1747 SlotIndex MBBEnd = Indexes->getMBBEndIdx(MBB); 1748 1749 // Scan Other.LI from VNI.def to MBBEnd. 1750 LiveInterval::iterator OtherI = Other.LI.find(VNI->def); 1751 assert(OtherI != Other.LI.end() && "No conflict?"); 1752 do { 1753 // OtherI is pointing to a tainted value. Abort the join if the tainted 1754 // lanes escape the block. 1755 SlotIndex End = OtherI->end; 1756 if (End >= MBBEnd) { 1757 DEBUG(dbgs() << "\t\ttaints global " << PrintReg(Other.LI.reg) << ':' 1758 << OtherI->valno->id << '@' << OtherI->start << '\n'); 1759 return false; 1760 } 1761 DEBUG(dbgs() << "\t\ttaints local " << PrintReg(Other.LI.reg) << ':' 1762 << OtherI->valno->id << '@' << OtherI->start 1763 << " to " << End << '\n'); 1764 // A dead def is not a problem. 1765 if (End.isDead()) 1766 break; 1767 TaintExtent.push_back(std::make_pair(End, TaintedLanes)); 1768 1769 // Check for another def in the MBB. 1770 if (++OtherI == Other.LI.end() || OtherI->start >= MBBEnd) 1771 break; 1772 1773 // Lanes written by the new def are no longer tainted. 1774 const Val &OV = Other.Vals[OtherI->valno->id]; 1775 TaintedLanes &= ~OV.WriteLanes; 1776 if (!OV.RedefVNI) 1777 break; 1778 } while (TaintedLanes); 1779 return true; 1780 } 1781 1782 /// Return true if MI uses any of the given Lanes from Reg. 1783 /// This does not include partial redefinitions of Reg. 1784 bool JoinVals::usesLanes(MachineInstr *MI, unsigned Reg, unsigned SubIdx, 1785 unsigned Lanes) { 1786 if (MI->isDebugValue()) 1787 return false; 1788 for (ConstMIOperands MO(MI); MO.isValid(); ++MO) { 1789 if (!MO->isReg() || MO->isDef() || MO->getReg() != Reg) 1790 continue; 1791 if (!MO->readsReg()) 1792 continue; 1793 if (Lanes & TRI->getSubRegIndexLaneMask( 1794 TRI->composeSubRegIndices(SubIdx, MO->getSubReg()))) 1795 return true; 1796 } 1797 return false; 1798 } 1799 1800 bool JoinVals::resolveConflicts(JoinVals &Other) { 1801 for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1802 Val &V = Vals[i]; 1803 assert (V.Resolution != CR_Impossible && "Unresolvable conflict"); 1804 if (V.Resolution != CR_Unresolved) 1805 continue; 1806 DEBUG(dbgs() << "\t\tconflict at " << PrintReg(LI.reg) << ':' << i 1807 << '@' << LI.getValNumInfo(i)->def << '\n'); 1808 ++NumLaneConflicts; 1809 assert(V.OtherVNI && "Inconsistent conflict resolution."); 1810 VNInfo *VNI = LI.getValNumInfo(i); 1811 const Val &OtherV = Other.Vals[V.OtherVNI->id]; 1812 1813 // VNI is known to clobber some lanes in OtherVNI. If we go ahead with the 1814 // join, those lanes will be tainted with a wrong value. Get the extent of 1815 // the tainted lanes. 1816 unsigned TaintedLanes = V.WriteLanes & OtherV.ValidLanes; 1817 SmallVector<std::pair<SlotIndex, unsigned>, 8> TaintExtent; 1818 if (!taintExtent(i, TaintedLanes, Other, TaintExtent)) 1819 // Tainted lanes would extend beyond the basic block. 1820 return false; 1821 1822 assert(!TaintExtent.empty() && "There should be at least one conflict."); 1823 1824 // Now look at the instructions from VNI->def to TaintExtent (inclusive). 1825 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1826 MachineBasicBlock::iterator MI = MBB->begin(); 1827 if (!VNI->isPHIDef()) { 1828 MI = Indexes->getInstructionFromIndex(VNI->def); 1829 // No need to check the instruction defining VNI for reads. 1830 ++MI; 1831 } 1832 assert(!SlotIndex::isSameInstr(VNI->def, TaintExtent.front().first) && 1833 "Interference ends on VNI->def. Should have been handled earlier"); 1834 MachineInstr *LastMI = 1835 Indexes->getInstructionFromIndex(TaintExtent.front().first); 1836 assert(LastMI && "Range must end at a proper instruction"); 1837 unsigned TaintNum = 0; 1838 for(;;) { 1839 assert(MI != MBB->end() && "Bad LastMI"); 1840 if (usesLanes(MI, Other.LI.reg, Other.SubIdx, TaintedLanes)) { 1841 DEBUG(dbgs() << "\t\ttainted lanes used by: " << *MI); 1842 return false; 1843 } 1844 // LastMI is the last instruction to use the current value. 1845 if (&*MI == LastMI) { 1846 if (++TaintNum == TaintExtent.size()) 1847 break; 1848 LastMI = Indexes->getInstructionFromIndex(TaintExtent[TaintNum].first); 1849 assert(LastMI && "Range must end at a proper instruction"); 1850 TaintedLanes = TaintExtent[TaintNum].second; 1851 } 1852 ++MI; 1853 } 1854 1855 // The tainted lanes are unused. 1856 V.Resolution = CR_Replace; 1857 ++NumLaneResolves; 1858 } 1859 return true; 1860 } 1861 1862 // Determine if ValNo is a copy of a value number in LI or Other.LI that will 1863 // be pruned: 1864 // 1865 // %dst = COPY %src 1866 // %src = COPY %dst <-- This value to be pruned. 1867 // %dst = COPY %src <-- This value is a copy of a pruned value. 1868 // 1869 bool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) { 1870 Val &V = Vals[ValNo]; 1871 if (V.Pruned || V.PrunedComputed) 1872 return V.Pruned; 1873 1874 if (V.Resolution != CR_Erase && V.Resolution != CR_Merge) 1875 return V.Pruned; 1876 1877 // Follow copies up the dominator tree and check if any intermediate value 1878 // has been pruned. 1879 V.PrunedComputed = true; 1880 V.Pruned = Other.isPrunedValue(V.OtherVNI->id, *this); 1881 return V.Pruned; 1882 } 1883 1884 void JoinVals::pruneValues(JoinVals &Other, 1885 SmallVectorImpl<SlotIndex> &EndPoints) { 1886 for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1887 SlotIndex Def = LI.getValNumInfo(i)->def; 1888 switch (Vals[i].Resolution) { 1889 case CR_Keep: 1890 break; 1891 case CR_Replace: { 1892 // This value takes precedence over the value in Other.LI. 1893 LIS->pruneValue(&Other.LI, Def, &EndPoints); 1894 // Check if we're replacing an IMPLICIT_DEF value. The IMPLICIT_DEF 1895 // instructions are only inserted to provide a live-out value for PHI 1896 // predecessors, so the instruction should simply go away once its value 1897 // has been replaced. 1898 Val &OtherV = Other.Vals[Vals[i].OtherVNI->id]; 1899 bool EraseImpDef = OtherV.ErasableImplicitDef && 1900 OtherV.Resolution == CR_Keep; 1901 if (!Def.isBlock()) { 1902 // Remove <def,read-undef> flags. This def is now a partial redef. 1903 // Also remove <def,dead> flags since the joined live range will 1904 // continue past this instruction. 1905 for (MIOperands MO(Indexes->getInstructionFromIndex(Def)); 1906 MO.isValid(); ++MO) 1907 if (MO->isReg() && MO->isDef() && MO->getReg() == LI.reg) { 1908 MO->setIsUndef(EraseImpDef); 1909 MO->setIsDead(false); 1910 } 1911 // This value will reach instructions below, but we need to make sure 1912 // the live range also reaches the instruction at Def. 1913 if (!EraseImpDef) 1914 EndPoints.push_back(Def); 1915 } 1916 DEBUG(dbgs() << "\t\tpruned " << PrintReg(Other.LI.reg) << " at " << Def 1917 << ": " << Other.LI << '\n'); 1918 break; 1919 } 1920 case CR_Erase: 1921 case CR_Merge: 1922 if (isPrunedValue(i, Other)) { 1923 // This value is ultimately a copy of a pruned value in LI or Other.LI. 1924 // We can no longer trust the value mapping computed by 1925 // computeAssignment(), the value that was originally copied could have 1926 // been replaced. 1927 LIS->pruneValue(&LI, Def, &EndPoints); 1928 DEBUG(dbgs() << "\t\tpruned all of " << PrintReg(LI.reg) << " at " 1929 << Def << ": " << LI << '\n'); 1930 } 1931 break; 1932 case CR_Unresolved: 1933 case CR_Impossible: 1934 llvm_unreachable("Unresolved conflicts"); 1935 } 1936 } 1937 } 1938 1939 void JoinVals::eraseInstrs(SmallPtrSet<MachineInstr*, 8> &ErasedInstrs, 1940 SmallVectorImpl<unsigned> &ShrinkRegs) { 1941 for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1942 // Get the def location before markUnused() below invalidates it. 1943 SlotIndex Def = LI.getValNumInfo(i)->def; 1944 switch (Vals[i].Resolution) { 1945 case CR_Keep: 1946 // If an IMPLICIT_DEF value is pruned, it doesn't serve a purpose any 1947 // longer. The IMPLICIT_DEF instructions are only inserted by 1948 // PHIElimination to guarantee that all PHI predecessors have a value. 1949 if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned) 1950 break; 1951 // Remove value number i from LI. Note that this VNInfo is still present 1952 // in NewVNInfo, so it will appear as an unused value number in the final 1953 // joined interval. 1954 LI.getValNumInfo(i)->markUnused(); 1955 LI.removeValNo(LI.getValNumInfo(i)); 1956 DEBUG(dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LI << '\n'); 1957 // FALL THROUGH. 1958 1959 case CR_Erase: { 1960 MachineInstr *MI = Indexes->getInstructionFromIndex(Def); 1961 assert(MI && "No instruction to erase"); 1962 if (MI->isCopy()) { 1963 unsigned Reg = MI->getOperand(1).getReg(); 1964 if (TargetRegisterInfo::isVirtualRegister(Reg) && 1965 Reg != CP.getSrcReg() && Reg != CP.getDstReg()) 1966 ShrinkRegs.push_back(Reg); 1967 } 1968 ErasedInstrs.insert(MI); 1969 DEBUG(dbgs() << "\t\terased:\t" << Def << '\t' << *MI); 1970 LIS->RemoveMachineInstrFromMaps(MI); 1971 MI->eraseFromParent(); 1972 break; 1973 } 1974 default: 1975 break; 1976 } 1977 } 1978 } 1979 1980 bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) { 1981 SmallVector<VNInfo*, 16> NewVNInfo; 1982 LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1983 LiveInterval &LHS = LIS->getInterval(CP.getDstReg()); 1984 JoinVals RHSVals(RHS, CP.getSrcIdx(), NewVNInfo, CP, LIS, TRI); 1985 JoinVals LHSVals(LHS, CP.getDstIdx(), NewVNInfo, CP, LIS, TRI); 1986 1987 DEBUG(dbgs() << "\t\tRHS = " << RHS 1988 << "\n\t\tLHS = " << LHS 1989 << '\n'); 1990 1991 // First compute NewVNInfo and the simple value mappings. 1992 // Detect impossible conflicts early. 1993 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) 1994 return false; 1995 1996 // Some conflicts can only be resolved after all values have been mapped. 1997 if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals)) 1998 return false; 1999 2000 // All clear, the live ranges can be merged. 2001 2002 // The merging algorithm in LiveInterval::join() can't handle conflicting 2003 // value mappings, so we need to remove any live ranges that overlap a 2004 // CR_Replace resolution. Collect a set of end points that can be used to 2005 // restore the live range after joining. 2006 SmallVector<SlotIndex, 8> EndPoints; 2007 LHSVals.pruneValues(RHSVals, EndPoints); 2008 RHSVals.pruneValues(LHSVals, EndPoints); 2009 2010 // Erase COPY and IMPLICIT_DEF instructions. This may cause some external 2011 // registers to require trimming. 2012 SmallVector<unsigned, 8> ShrinkRegs; 2013 LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs); 2014 RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs); 2015 while (!ShrinkRegs.empty()) 2016 LIS->shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val())); 2017 2018 // Join RHS into LHS. 2019 LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo); 2020 2021 // Kill flags are going to be wrong if the live ranges were overlapping. 2022 // Eventually, we should simply clear all kill flags when computing live 2023 // ranges. They are reinserted after register allocation. 2024 MRI->clearKillFlags(LHS.reg); 2025 MRI->clearKillFlags(RHS.reg); 2026 2027 if (EndPoints.empty()) 2028 return true; 2029 2030 // Recompute the parts of the live range we had to remove because of 2031 // CR_Replace conflicts. 2032 DEBUG(dbgs() << "\t\trestoring liveness to " << EndPoints.size() 2033 << " points: " << LHS << '\n'); 2034 LIS->extendToIndices(LHS, EndPoints); 2035 return true; 2036 } 2037 2038 /// joinIntervals - Attempt to join these two intervals. On failure, this 2039 /// returns false. 2040 bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) { 2041 return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP); 2042 } 2043 2044 namespace { 2045 // Information concerning MBB coalescing priority. 2046 struct MBBPriorityInfo { 2047 MachineBasicBlock *MBB; 2048 unsigned Depth; 2049 bool IsSplit; 2050 2051 MBBPriorityInfo(MachineBasicBlock *mbb, unsigned depth, bool issplit) 2052 : MBB(mbb), Depth(depth), IsSplit(issplit) {} 2053 }; 2054 } 2055 2056 // C-style comparator that sorts first based on the loop depth of the basic 2057 // block (the unsigned), and then on the MBB number. 2058 // 2059 // EnableGlobalCopies assumes that the primary sort key is loop depth. 2060 static int compareMBBPriority(const MBBPriorityInfo *LHS, 2061 const MBBPriorityInfo *RHS) { 2062 // Deeper loops first 2063 if (LHS->Depth != RHS->Depth) 2064 return LHS->Depth > RHS->Depth ? -1 : 1; 2065 2066 // Try to unsplit critical edges next. 2067 if (LHS->IsSplit != RHS->IsSplit) 2068 return LHS->IsSplit ? -1 : 1; 2069 2070 // Prefer blocks that are more connected in the CFG. This takes care of 2071 // the most difficult copies first while intervals are short. 2072 unsigned cl = LHS->MBB->pred_size() + LHS->MBB->succ_size(); 2073 unsigned cr = RHS->MBB->pred_size() + RHS->MBB->succ_size(); 2074 if (cl != cr) 2075 return cl > cr ? -1 : 1; 2076 2077 // As a last resort, sort by block number. 2078 return LHS->MBB->getNumber() < RHS->MBB->getNumber() ? -1 : 1; 2079 } 2080 2081 /// \returns true if the given copy uses or defines a local live range. 2082 static bool isLocalCopy(MachineInstr *Copy, const LiveIntervals *LIS) { 2083 if (!Copy->isCopy()) 2084 return false; 2085 2086 if (Copy->getOperand(1).isUndef()) 2087 return false; 2088 2089 unsigned SrcReg = Copy->getOperand(1).getReg(); 2090 unsigned DstReg = Copy->getOperand(0).getReg(); 2091 if (TargetRegisterInfo::isPhysicalRegister(SrcReg) 2092 || TargetRegisterInfo::isPhysicalRegister(DstReg)) 2093 return false; 2094 2095 return LIS->intervalIsInOneMBB(LIS->getInterval(SrcReg)) 2096 || LIS->intervalIsInOneMBB(LIS->getInterval(DstReg)); 2097 } 2098 2099 // Try joining WorkList copies starting from index From. 2100 // Null out any successful joins. 2101 bool RegisterCoalescer:: 2102 copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList) { 2103 bool Progress = false; 2104 for (unsigned i = 0, e = CurrList.size(); i != e; ++i) { 2105 if (!CurrList[i]) 2106 continue; 2107 // Skip instruction pointers that have already been erased, for example by 2108 // dead code elimination. 2109 if (ErasedInstrs.erase(CurrList[i])) { 2110 CurrList[i] = nullptr; 2111 continue; 2112 } 2113 bool Again = false; 2114 bool Success = joinCopy(CurrList[i], Again); 2115 Progress |= Success; 2116 if (Success || !Again) 2117 CurrList[i] = nullptr; 2118 } 2119 return Progress; 2120 } 2121 2122 void 2123 RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) { 2124 DEBUG(dbgs() << MBB->getName() << ":\n"); 2125 2126 // Collect all copy-like instructions in MBB. Don't start coalescing anything 2127 // yet, it might invalidate the iterator. 2128 const unsigned PrevSize = WorkList.size(); 2129 if (JoinGlobalCopies) { 2130 // Coalesce copies bottom-up to coalesce local defs before local uses. They 2131 // are not inherently easier to resolve, but slightly preferable until we 2132 // have local live range splitting. In particular this is required by 2133 // cmp+jmp macro fusion. 2134 for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 2135 MII != E; ++MII) { 2136 if (!MII->isCopyLike()) 2137 continue; 2138 if (isLocalCopy(&(*MII), LIS)) 2139 LocalWorkList.push_back(&(*MII)); 2140 else 2141 WorkList.push_back(&(*MII)); 2142 } 2143 } 2144 else { 2145 for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 2146 MII != E; ++MII) 2147 if (MII->isCopyLike()) 2148 WorkList.push_back(MII); 2149 } 2150 // Try coalescing the collected copies immediately, and remove the nulls. 2151 // This prevents the WorkList from getting too large since most copies are 2152 // joinable on the first attempt. 2153 MutableArrayRef<MachineInstr*> 2154 CurrList(WorkList.begin() + PrevSize, WorkList.end()); 2155 if (copyCoalesceWorkList(CurrList)) 2156 WorkList.erase(std::remove(WorkList.begin() + PrevSize, WorkList.end(), 2157 (MachineInstr*)nullptr), WorkList.end()); 2158 } 2159 2160 void RegisterCoalescer::coalesceLocals() { 2161 copyCoalesceWorkList(LocalWorkList); 2162 for (unsigned j = 0, je = LocalWorkList.size(); j != je; ++j) { 2163 if (LocalWorkList[j]) 2164 WorkList.push_back(LocalWorkList[j]); 2165 } 2166 LocalWorkList.clear(); 2167 } 2168 2169 void RegisterCoalescer::joinAllIntervals() { 2170 DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n"); 2171 assert(WorkList.empty() && LocalWorkList.empty() && "Old data still around."); 2172 2173 std::vector<MBBPriorityInfo> MBBs; 2174 MBBs.reserve(MF->size()); 2175 for (MachineFunction::iterator I = MF->begin(), E = MF->end();I != E;++I){ 2176 MachineBasicBlock *MBB = I; 2177 MBBs.push_back(MBBPriorityInfo(MBB, Loops->getLoopDepth(MBB), 2178 JoinSplitEdges && isSplitEdge(MBB))); 2179 } 2180 array_pod_sort(MBBs.begin(), MBBs.end(), compareMBBPriority); 2181 2182 // Coalesce intervals in MBB priority order. 2183 unsigned CurrDepth = UINT_MAX; 2184 for (unsigned i = 0, e = MBBs.size(); i != e; ++i) { 2185 // Try coalescing the collected local copies for deeper loops. 2186 if (JoinGlobalCopies && MBBs[i].Depth < CurrDepth) { 2187 coalesceLocals(); 2188 CurrDepth = MBBs[i].Depth; 2189 } 2190 copyCoalesceInMBB(MBBs[i].MBB); 2191 } 2192 coalesceLocals(); 2193 2194 // Joining intervals can allow other intervals to be joined. Iteratively join 2195 // until we make no progress. 2196 while (copyCoalesceWorkList(WorkList)) 2197 /* empty */ ; 2198 } 2199 2200 void RegisterCoalescer::releaseMemory() { 2201 ErasedInstrs.clear(); 2202 WorkList.clear(); 2203 DeadDefs.clear(); 2204 InflateRegs.clear(); 2205 } 2206 2207 bool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) { 2208 MF = &fn; 2209 MRI = &fn.getRegInfo(); 2210 TM = &fn.getTarget(); 2211 TRI = TM->getRegisterInfo(); 2212 TII = TM->getInstrInfo(); 2213 LIS = &getAnalysis<LiveIntervals>(); 2214 AA = &getAnalysis<AliasAnalysis>(); 2215 Loops = &getAnalysis<MachineLoopInfo>(); 2216 2217 const TargetSubtargetInfo &ST = TM->getSubtarget<TargetSubtargetInfo>(); 2218 if (EnableGlobalCopies == cl::BOU_UNSET) 2219 JoinGlobalCopies = ST.useMachineScheduler(); 2220 else 2221 JoinGlobalCopies = (EnableGlobalCopies == cl::BOU_TRUE); 2222 2223 // The MachineScheduler does not currently require JoinSplitEdges. This will 2224 // either be enabled unconditionally or replaced by a more general live range 2225 // splitting optimization. 2226 JoinSplitEdges = EnableJoinSplits; 2227 2228 DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n" 2229 << "********** Function: " << MF->getName() << '\n'); 2230 2231 if (VerifyCoalescing) 2232 MF->verify(this, "Before register coalescing"); 2233 2234 RegClassInfo.runOnMachineFunction(fn); 2235 2236 // Join (coalesce) intervals if requested. 2237 if (EnableJoining) 2238 joinAllIntervals(); 2239 2240 // After deleting a lot of copies, register classes may be less constrained. 2241 // Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 -> 2242 // DPR inflation. 2243 array_pod_sort(InflateRegs.begin(), InflateRegs.end()); 2244 InflateRegs.erase(std::unique(InflateRegs.begin(), InflateRegs.end()), 2245 InflateRegs.end()); 2246 DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size() << " regs.\n"); 2247 for (unsigned i = 0, e = InflateRegs.size(); i != e; ++i) { 2248 unsigned Reg = InflateRegs[i]; 2249 if (MRI->reg_nodbg_empty(Reg)) 2250 continue; 2251 if (MRI->recomputeRegClass(Reg, *TM)) { 2252 DEBUG(dbgs() << PrintReg(Reg) << " inflated to " 2253 << MRI->getRegClass(Reg)->getName() << '\n'); 2254 ++NumInflated; 2255 } 2256 } 2257 2258 DEBUG(dump()); 2259 if (VerifyCoalescing) 2260 MF->verify(this, "After register coalescing"); 2261 return true; 2262 } 2263 2264 /// print - Implement the dump method. 2265 void RegisterCoalescer::print(raw_ostream &O, const Module* m) const { 2266 LIS->print(O, m); 2267 } 2268