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