RegisterCoalescer.cpp revision b77ec7d26405125fa5685370af5f17fcc9edbecd
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 "RegisterClassInfo.h" 20#include "VirtRegMap.h" 21 22#include "llvm/Pass.h" 23#include "llvm/Value.h" 24#include "llvm/ADT/OwningPtr.h" 25#include "llvm/ADT/STLExtras.h" 26#include "llvm/ADT/SmallSet.h" 27#include "llvm/ADT/Statistic.h" 28#include "llvm/Analysis/AliasAnalysis.h" 29#include "llvm/CodeGen/LiveIntervalAnalysis.h" 30#include "llvm/CodeGen/LiveIntervalAnalysis.h" 31#include "llvm/CodeGen/LiveRangeEdit.h" 32#include "llvm/CodeGen/MachineFrameInfo.h" 33#include "llvm/CodeGen/MachineInstr.h" 34#include "llvm/CodeGen/MachineInstr.h" 35#include "llvm/CodeGen/MachineLoopInfo.h" 36#include "llvm/CodeGen/MachineRegisterInfo.h" 37#include "llvm/CodeGen/MachineRegisterInfo.h" 38#include "llvm/CodeGen/Passes.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 <algorithm> 49#include <cmath> 50using namespace llvm; 51 52STATISTIC(numJoins , "Number of interval joins performed"); 53STATISTIC(numCrossRCs , "Number of cross class joins performed"); 54STATISTIC(numCommutes , "Number of instruction commuting performed"); 55STATISTIC(numExtends , "Number of copies extended"); 56STATISTIC(NumReMats , "Number of instructions re-materialized"); 57STATISTIC(NumInflated , "Number of register classes inflated"); 58 59static cl::opt<bool> 60EnableJoining("join-liveintervals", 61 cl::desc("Coalesce copies (default=true)"), 62 cl::init(true)); 63 64static cl::opt<bool> 65VerifyCoalescing("verify-coalescing", 66 cl::desc("Verify machine instrs before and after register coalescing"), 67 cl::Hidden); 68 69namespace { 70 class RegisterCoalescer : public MachineFunctionPass, 71 private LiveRangeEdit::Delegate { 72 MachineFunction* MF; 73 MachineRegisterInfo* MRI; 74 const TargetMachine* TM; 75 const TargetRegisterInfo* TRI; 76 const TargetInstrInfo* TII; 77 LiveIntervals *LIS; 78 LiveDebugVariables *LDV; 79 const MachineLoopInfo* Loops; 80 AliasAnalysis *AA; 81 RegisterClassInfo RegClassInfo; 82 83 /// WorkList - Copy instructions yet to be coalesced. 84 SmallVector<MachineInstr*, 8> WorkList; 85 86 /// ErasedInstrs - Set of instruction pointers that have been erased, and 87 /// that may be present in WorkList. 88 SmallPtrSet<MachineInstr*, 8> ErasedInstrs; 89 90 /// Dead instructions that are about to be deleted. 91 SmallVector<MachineInstr*, 8> DeadDefs; 92 93 /// Virtual registers to be considered for register class inflation. 94 SmallVector<unsigned, 8> InflateRegs; 95 96 /// Recursively eliminate dead defs in DeadDefs. 97 void eliminateDeadDefs(); 98 99 /// LiveRangeEdit callback. 100 void LRE_WillEraseInstruction(MachineInstr *MI); 101 102 /// joinAllIntervals - join compatible live intervals 103 void joinAllIntervals(); 104 105 /// copyCoalesceInMBB - Coalesce copies in the specified MBB, putting 106 /// copies that cannot yet be coalesced into WorkList. 107 void copyCoalesceInMBB(MachineBasicBlock *MBB); 108 109 /// copyCoalesceWorkList - Try to coalesce all copies in WorkList after 110 /// position From. Return true if any progress was made. 111 bool copyCoalesceWorkList(unsigned From = 0); 112 113 /// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 114 /// which are the src/dst of the copy instruction CopyMI. This returns 115 /// true if the copy was successfully coalesced away. If it is not 116 /// currently possible to coalesce this interval, but it may be possible if 117 /// other things get coalesced, then it returns true by reference in 118 /// 'Again'. 119 bool joinCopy(MachineInstr *TheCopy, bool &Again); 120 121 /// joinIntervals - Attempt to join these two intervals. On failure, this 122 /// returns false. The output "SrcInt" will not have been modified, so we 123 /// can use this information below to update aliases. 124 bool joinIntervals(CoalescerPair &CP); 125 126 /// Attempt joining with a reserved physreg. 127 bool joinReservedPhysReg(CoalescerPair &CP); 128 129 /// adjustCopiesBackFrom - We found a non-trivially-coalescable copy. If 130 /// the source value number is defined by a copy from the destination reg 131 /// see if we can merge these two destination reg valno# into a single 132 /// value number, eliminating a copy. 133 bool adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI); 134 135 /// hasOtherReachingDefs - Return true if there are definitions of IntB 136 /// other than BValNo val# that can reach uses of AValno val# of IntA. 137 bool hasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB, 138 VNInfo *AValNo, VNInfo *BValNo); 139 140 /// removeCopyByCommutingDef - We found a non-trivially-coalescable copy. 141 /// If the source value number is defined by a commutable instruction and 142 /// its other operand is coalesced to the copy dest register, see if we 143 /// can transform the copy into a noop by commuting the definition. 144 bool removeCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI); 145 146 /// reMaterializeTrivialDef - If the source of a copy is defined by a 147 /// trivial computation, replace the copy by rematerialize the definition. 148 bool reMaterializeTrivialDef(LiveInterval &SrcInt, unsigned DstReg, 149 MachineInstr *CopyMI); 150 151 /// canJoinPhys - Return true if a physreg copy should be joined. 152 bool canJoinPhys(CoalescerPair &CP); 153 154 /// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 155 /// update the subregister number if it is not zero. If DstReg is a 156 /// physical register and the existing subregister number of the def / use 157 /// being updated is not zero, make sure to set it to the correct physical 158 /// subregister. 159 void updateRegDefsUses(unsigned SrcReg, unsigned DstReg, unsigned SubIdx); 160 161 /// eliminateUndefCopy - Handle copies of undef values. 162 bool eliminateUndefCopy(MachineInstr *CopyMI, const CoalescerPair &CP); 163 164 public: 165 static char ID; // Class identification, replacement for typeinfo 166 RegisterCoalescer() : MachineFunctionPass(ID) { 167 initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 168 } 169 170 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 171 172 virtual void releaseMemory(); 173 174 /// runOnMachineFunction - pass entry point 175 virtual bool runOnMachineFunction(MachineFunction&); 176 177 /// print - Implement the dump method. 178 virtual void print(raw_ostream &O, const Module* = 0) const; 179 }; 180} /// end anonymous namespace 181 182char &llvm::RegisterCoalescerID = RegisterCoalescer::ID; 183 184INITIALIZE_PASS_BEGIN(RegisterCoalescer, "simple-register-coalescing", 185 "Simple Register Coalescing", false, false) 186INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 187INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) 188INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 189INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 190INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 191INITIALIZE_PASS_END(RegisterCoalescer, "simple-register-coalescing", 192 "Simple Register Coalescing", false, false) 193 194char RegisterCoalescer::ID = 0; 195 196static unsigned compose(const TargetRegisterInfo &tri, unsigned a, unsigned b) { 197 if (!a) return b; 198 if (!b) return a; 199 return tri.composeSubRegIndices(a, b); 200} 201 202static bool isMoveInstr(const TargetRegisterInfo &tri, const MachineInstr *MI, 203 unsigned &Src, unsigned &Dst, 204 unsigned &SrcSub, unsigned &DstSub) { 205 if (MI->isCopy()) { 206 Dst = MI->getOperand(0).getReg(); 207 DstSub = MI->getOperand(0).getSubReg(); 208 Src = MI->getOperand(1).getReg(); 209 SrcSub = MI->getOperand(1).getSubReg(); 210 } else if (MI->isSubregToReg()) { 211 Dst = MI->getOperand(0).getReg(); 212 DstSub = compose(tri, MI->getOperand(0).getSubReg(), 213 MI->getOperand(3).getImm()); 214 Src = MI->getOperand(2).getReg(); 215 SrcSub = MI->getOperand(2).getSubReg(); 216 } else 217 return false; 218 return true; 219} 220 221bool CoalescerPair::setRegisters(const MachineInstr *MI) { 222 SrcReg = DstReg = 0; 223 SrcIdx = DstIdx = 0; 224 NewRC = 0; 225 Flipped = CrossClass = false; 226 227 unsigned Src, Dst, SrcSub, DstSub; 228 if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 229 return false; 230 Partial = SrcSub || DstSub; 231 232 // If one register is a physreg, it must be Dst. 233 if (TargetRegisterInfo::isPhysicalRegister(Src)) { 234 if (TargetRegisterInfo::isPhysicalRegister(Dst)) 235 return false; 236 std::swap(Src, Dst); 237 std::swap(SrcSub, DstSub); 238 Flipped = true; 239 } 240 241 const MachineRegisterInfo &MRI = MI->getParent()->getParent()->getRegInfo(); 242 243 if (TargetRegisterInfo::isPhysicalRegister(Dst)) { 244 // Eliminate DstSub on a physreg. 245 if (DstSub) { 246 Dst = TRI.getSubReg(Dst, DstSub); 247 if (!Dst) return false; 248 DstSub = 0; 249 } 250 251 // Eliminate SrcSub by picking a corresponding Dst superregister. 252 if (SrcSub) { 253 Dst = TRI.getMatchingSuperReg(Dst, SrcSub, MRI.getRegClass(Src)); 254 if (!Dst) return false; 255 SrcSub = 0; 256 } else if (!MRI.getRegClass(Src)->contains(Dst)) { 257 return false; 258 } 259 } else { 260 // Both registers are virtual. 261 const TargetRegisterClass *SrcRC = MRI.getRegClass(Src); 262 const TargetRegisterClass *DstRC = MRI.getRegClass(Dst); 263 264 // Both registers have subreg indices. 265 if (SrcSub && DstSub) { 266 // Copies between different sub-registers are never coalescable. 267 if (Src == Dst && SrcSub != DstSub) 268 return false; 269 270 NewRC = TRI.getCommonSuperRegClass(SrcRC, SrcSub, DstRC, DstSub, 271 SrcIdx, DstIdx); 272 if (!NewRC) 273 return false; 274 } else if (DstSub) { 275 // SrcReg will be merged with a sub-register of DstReg. 276 SrcIdx = DstSub; 277 NewRC = TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub); 278 } else if (SrcSub) { 279 // DstReg will be merged with a sub-register of SrcReg. 280 DstIdx = SrcSub; 281 NewRC = TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSub); 282 } else { 283 // This is a straight copy without sub-registers. 284 NewRC = TRI.getCommonSubClass(DstRC, SrcRC); 285 } 286 287 // The combined constraint may be impossible to satisfy. 288 if (!NewRC) 289 return false; 290 291 // Prefer SrcReg to be a sub-register of DstReg. 292 // FIXME: Coalescer should support subregs symmetrically. 293 if (DstIdx && !SrcIdx) { 294 std::swap(Src, Dst); 295 std::swap(SrcIdx, DstIdx); 296 Flipped = !Flipped; 297 } 298 299 CrossClass = NewRC != DstRC || NewRC != SrcRC; 300 } 301 // Check our invariants 302 assert(TargetRegisterInfo::isVirtualRegister(Src) && "Src must be virtual"); 303 assert(!(TargetRegisterInfo::isPhysicalRegister(Dst) && DstSub) && 304 "Cannot have a physical SubIdx"); 305 SrcReg = Src; 306 DstReg = Dst; 307 return true; 308} 309 310bool CoalescerPair::flip() { 311 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) 312 return false; 313 std::swap(SrcReg, DstReg); 314 std::swap(SrcIdx, DstIdx); 315 Flipped = !Flipped; 316 return true; 317} 318 319bool CoalescerPair::isCoalescable(const MachineInstr *MI) const { 320 if (!MI) 321 return false; 322 unsigned Src, Dst, SrcSub, DstSub; 323 if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 324 return false; 325 326 // Find the virtual register that is SrcReg. 327 if (Dst == SrcReg) { 328 std::swap(Src, Dst); 329 std::swap(SrcSub, DstSub); 330 } else if (Src != SrcReg) { 331 return false; 332 } 333 334 // Now check that Dst matches DstReg. 335 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { 336 if (!TargetRegisterInfo::isPhysicalRegister(Dst)) 337 return false; 338 assert(!DstIdx && !SrcIdx && "Inconsistent CoalescerPair state."); 339 // DstSub could be set for a physreg from INSERT_SUBREG. 340 if (DstSub) 341 Dst = TRI.getSubReg(Dst, DstSub); 342 // Full copy of Src. 343 if (!SrcSub) 344 return DstReg == Dst; 345 // This is a partial register copy. Check that the parts match. 346 return TRI.getSubReg(DstReg, SrcSub) == Dst; 347 } else { 348 // DstReg is virtual. 349 if (DstReg != Dst) 350 return false; 351 // Registers match, do the subregisters line up? 352 return compose(TRI, SrcIdx, SrcSub) == compose(TRI, DstIdx, DstSub); 353 } 354} 355 356void RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const { 357 AU.setPreservesCFG(); 358 AU.addRequired<AliasAnalysis>(); 359 AU.addRequired<LiveIntervals>(); 360 AU.addPreserved<LiveIntervals>(); 361 AU.addRequired<LiveDebugVariables>(); 362 AU.addPreserved<LiveDebugVariables>(); 363 AU.addPreserved<SlotIndexes>(); 364 AU.addRequired<MachineLoopInfo>(); 365 AU.addPreserved<MachineLoopInfo>(); 366 AU.addPreservedID(MachineDominatorsID); 367 MachineFunctionPass::getAnalysisUsage(AU); 368} 369 370void RegisterCoalescer::eliminateDeadDefs() { 371 SmallVector<LiveInterval*, 8> NewRegs; 372 LiveRangeEdit(0, NewRegs, *MF, *LIS, 0, this).eliminateDeadDefs(DeadDefs); 373} 374 375// Callback from eliminateDeadDefs(). 376void RegisterCoalescer::LRE_WillEraseInstruction(MachineInstr *MI) { 377 // MI may be in WorkList. Make sure we don't visit it. 378 ErasedInstrs.insert(MI); 379} 380 381/// adjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA 382/// being the source and IntB being the dest, thus this defines a value number 383/// in IntB. If the source value number (in IntA) is defined by a copy from B, 384/// see if we can merge these two pieces of B into a single value number, 385/// eliminating a copy. For example: 386/// 387/// A3 = B0 388/// ... 389/// B1 = A3 <- this copy 390/// 391/// In this case, B0 can be extended to where the B1 copy lives, allowing the B1 392/// value number to be replaced with B0 (which simplifies the B liveinterval). 393/// 394/// This returns true if an interval was modified. 395/// 396bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP, 397 MachineInstr *CopyMI) { 398 assert(!CP.isPartial() && "This doesn't work for partial copies."); 399 assert(!CP.isPhys() && "This doesn't work for physreg copies."); 400 401 // Bail if there is no dst interval - can happen when merging physical subreg 402 // operations. 403 if (!LIS->hasInterval(CP.getDstReg())) 404 return false; 405 406 LiveInterval &IntA = 407 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 408 LiveInterval &IntB = 409 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 410 SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 411 412 // BValNo is a value number in B that is defined by a copy from A. 'B3' in 413 // the example above. 414 LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); 415 if (BLR == IntB.end()) return false; 416 VNInfo *BValNo = BLR->valno; 417 418 // Get the location that B is defined at. Two options: either this value has 419 // an unknown definition point or it is defined at CopyIdx. If unknown, we 420 // can't process it. 421 if (BValNo->def != CopyIdx) return false; 422 423 // AValNo is the value number in A that defines the copy, A3 in the example. 424 SlotIndex CopyUseIdx = CopyIdx.getRegSlot(true); 425 LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx); 426 // The live range might not exist after fun with physreg coalescing. 427 if (ALR == IntA.end()) return false; 428 VNInfo *AValNo = ALR->valno; 429 430 // If AValNo is defined as a copy from IntB, we can potentially process this. 431 // Get the instruction that defines this value number. 432 MachineInstr *ACopyMI = LIS->getInstructionFromIndex(AValNo->def); 433 if (!CP.isCoalescable(ACopyMI)) 434 return false; 435 436 // Get the LiveRange in IntB that this value number starts with. 437 LiveInterval::iterator ValLR = 438 IntB.FindLiveRangeContaining(AValNo->def.getPrevSlot()); 439 if (ValLR == IntB.end()) 440 return false; 441 442 // Make sure that the end of the live range is inside the same block as 443 // CopyMI. 444 MachineInstr *ValLREndInst = 445 LIS->getInstructionFromIndex(ValLR->end.getPrevSlot()); 446 if (!ValLREndInst || ValLREndInst->getParent() != CopyMI->getParent()) 447 return false; 448 449 // Okay, we now know that ValLR ends in the same block that the CopyMI 450 // live-range starts. If there are no intervening live ranges between them in 451 // IntB, we can merge them. 452 if (ValLR+1 != BLR) return false; 453 454 DEBUG(dbgs() << "Extending: " << PrintReg(IntB.reg, TRI)); 455 456 SlotIndex FillerStart = ValLR->end, FillerEnd = BLR->start; 457 // We are about to delete CopyMI, so need to remove it as the 'instruction 458 // that defines this value #'. Update the valnum with the new defining 459 // instruction #. 460 BValNo->def = FillerStart; 461 462 // Okay, we can merge them. We need to insert a new liverange: 463 // [ValLR.end, BLR.begin) of either value number, then we merge the 464 // two value numbers. 465 IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo)); 466 467 // If the IntB live range is assigned to a physical register, and if that 468 // physreg has sub-registers, update their live intervals as well. 469 if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) { 470 for (MCSubRegIterator SR(IntB.reg, TRI); SR.isValid(); ++SR) { 471 if (!LIS->hasInterval(*SR)) 472 continue; 473 LiveInterval &SRLI = LIS->getInterval(*SR); 474 SRLI.addRange(LiveRange(FillerStart, FillerEnd, 475 SRLI.getNextValue(FillerStart, 476 LIS->getVNInfoAllocator()))); 477 } 478 } 479 480 // Okay, merge "B1" into the same value number as "B0". 481 if (BValNo != ValLR->valno) { 482 // If B1 is killed by a PHI, then the merged live range must also be killed 483 // by the same PHI, as B0 and B1 can not overlap. 484 bool HasPHIKill = BValNo->hasPHIKill(); 485 IntB.MergeValueNumberInto(BValNo, ValLR->valno); 486 if (HasPHIKill) 487 ValLR->valno->setHasPHIKill(true); 488 } 489 DEBUG(dbgs() << " result = " << IntB << '\n'); 490 491 // If the source instruction was killing the source register before the 492 // merge, unset the isKill marker given the live range has been extended. 493 int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true); 494 if (UIdx != -1) { 495 ValLREndInst->getOperand(UIdx).setIsKill(false); 496 } 497 498 // Rewrite the copy. If the copy instruction was killing the destination 499 // register before the merge, find the last use and trim the live range. That 500 // will also add the isKill marker. 501 CopyMI->substituteRegister(IntA.reg, IntB.reg, 0, *TRI); 502 if (ALR->end == CopyIdx) 503 LIS->shrinkToUses(&IntA); 504 505 ++numExtends; 506 return true; 507} 508 509/// hasOtherReachingDefs - Return true if there are definitions of IntB 510/// other than BValNo val# that can reach uses of AValno val# of IntA. 511bool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA, 512 LiveInterval &IntB, 513 VNInfo *AValNo, 514 VNInfo *BValNo) { 515 for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 516 AI != AE; ++AI) { 517 if (AI->valno != AValNo) continue; 518 LiveInterval::Ranges::iterator BI = 519 std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start); 520 if (BI != IntB.ranges.begin()) 521 --BI; 522 for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) { 523 if (BI->valno == BValNo) 524 continue; 525 if (BI->start <= AI->start && BI->end > AI->start) 526 return true; 527 if (BI->start > AI->start && BI->start < AI->end) 528 return true; 529 } 530 } 531 return false; 532} 533 534/// removeCopyByCommutingDef - We found a non-trivially-coalescable copy with 535/// IntA being the source and IntB being the dest, thus this defines a value 536/// number in IntB. If the source value number (in IntA) is defined by a 537/// commutable instruction and its other operand is coalesced to the copy dest 538/// register, see if we can transform the copy into a noop by commuting the 539/// definition. For example, 540/// 541/// A3 = op A2 B0<kill> 542/// ... 543/// B1 = A3 <- this copy 544/// ... 545/// = op A3 <- more uses 546/// 547/// ==> 548/// 549/// B2 = op B0 A2<kill> 550/// ... 551/// B1 = B2 <- now an identify copy 552/// ... 553/// = op B2 <- more uses 554/// 555/// This returns true if an interval was modified. 556/// 557bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, 558 MachineInstr *CopyMI) { 559 assert (!CP.isPhys()); 560 561 // Bail if there is no dst interval. 562 if (!LIS->hasInterval(CP.getDstReg())) 563 return false; 564 565 SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 566 567 LiveInterval &IntA = 568 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 569 LiveInterval &IntB = 570 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 571 572 // BValNo is a value number in B that is defined by a copy from A. 'B3' in 573 // the example above. 574 VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx); 575 if (!BValNo || BValNo->def != CopyIdx) 576 return false; 577 578 assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); 579 580 // AValNo is the value number in A that defines the copy, A3 in the example. 581 VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true)); 582 assert(AValNo && "COPY source not live"); 583 584 // If other defs can reach uses of this def, then it's not safe to perform 585 // the optimization. 586 if (AValNo->isPHIDef() || AValNo->isUnused() || AValNo->hasPHIKill()) 587 return false; 588 MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def); 589 if (!DefMI) 590 return false; 591 if (!DefMI->isCommutable()) 592 return false; 593 // If DefMI is a two-address instruction then commuting it will change the 594 // destination register. 595 int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg); 596 assert(DefIdx != -1); 597 unsigned UseOpIdx; 598 if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx)) 599 return false; 600 unsigned Op1, Op2, NewDstIdx; 601 if (!TII->findCommutedOpIndices(DefMI, Op1, Op2)) 602 return false; 603 if (Op1 == UseOpIdx) 604 NewDstIdx = Op2; 605 else if (Op2 == UseOpIdx) 606 NewDstIdx = Op1; 607 else 608 return false; 609 610 MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); 611 unsigned NewReg = NewDstMO.getReg(); 612 if (NewReg != IntB.reg || !NewDstMO.isKill()) 613 return false; 614 615 // Make sure there are no other definitions of IntB that would reach the 616 // uses which the new definition can reach. 617 if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo)) 618 return false; 619 620 // If some of the uses of IntA.reg is already coalesced away, return false. 621 // It's not possible to determine whether it's safe to perform the coalescing. 622 for (MachineRegisterInfo::use_nodbg_iterator UI = 623 MRI->use_nodbg_begin(IntA.reg), 624 UE = MRI->use_nodbg_end(); UI != UE; ++UI) { 625 MachineInstr *UseMI = &*UI; 626 SlotIndex UseIdx = LIS->getInstructionIndex(UseMI); 627 LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 628 if (ULR == IntA.end() || ULR->valno != AValNo) 629 continue; 630 // If this use is tied to a def, we can't rewrite the register. 631 if (UseMI->isRegTiedToDefOperand(UI.getOperandNo())) 632 return false; 633 } 634 635 DEBUG(dbgs() << "\tremoveCopyByCommutingDef: " << AValNo->def << '\t' 636 << *DefMI); 637 638 // At this point we have decided that it is legal to do this 639 // transformation. Start by commuting the instruction. 640 MachineBasicBlock *MBB = DefMI->getParent(); 641 MachineInstr *NewMI = TII->commuteInstruction(DefMI); 642 if (!NewMI) 643 return false; 644 if (TargetRegisterInfo::isVirtualRegister(IntA.reg) && 645 TargetRegisterInfo::isVirtualRegister(IntB.reg) && 646 !MRI->constrainRegClass(IntB.reg, MRI->getRegClass(IntA.reg))) 647 return false; 648 if (NewMI != DefMI) { 649 LIS->ReplaceMachineInstrInMaps(DefMI, NewMI); 650 MachineBasicBlock::iterator Pos = DefMI; 651 MBB->insert(Pos, NewMI); 652 MBB->erase(DefMI); 653 } 654 unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false); 655 NewMI->getOperand(OpIdx).setIsKill(); 656 657 // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g. 658 // A = or A, B 659 // ... 660 // B = A 661 // ... 662 // C = A<kill> 663 // ... 664 // = B 665 666 // Update uses of IntA of the specific Val# with IntB. 667 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(IntA.reg), 668 UE = MRI->use_end(); UI != UE;) { 669 MachineOperand &UseMO = UI.getOperand(); 670 MachineInstr *UseMI = &*UI; 671 ++UI; 672 if (UseMI->isDebugValue()) { 673 // FIXME These don't have an instruction index. Not clear we have enough 674 // info to decide whether to do this replacement or not. For now do it. 675 UseMO.setReg(NewReg); 676 continue; 677 } 678 SlotIndex UseIdx = LIS->getInstructionIndex(UseMI).getRegSlot(true); 679 LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 680 if (ULR == IntA.end() || ULR->valno != AValNo) 681 continue; 682 if (TargetRegisterInfo::isPhysicalRegister(NewReg)) 683 UseMO.substPhysReg(NewReg, *TRI); 684 else 685 UseMO.setReg(NewReg); 686 if (UseMI == CopyMI) 687 continue; 688 if (!UseMI->isCopy()) 689 continue; 690 if (UseMI->getOperand(0).getReg() != IntB.reg || 691 UseMI->getOperand(0).getSubReg()) 692 continue; 693 694 // This copy will become a noop. If it's defining a new val#, merge it into 695 // BValNo. 696 SlotIndex DefIdx = UseIdx.getRegSlot(); 697 VNInfo *DVNI = IntB.getVNInfoAt(DefIdx); 698 if (!DVNI) 699 continue; 700 DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI); 701 assert(DVNI->def == DefIdx); 702 BValNo = IntB.MergeValueNumberInto(BValNo, DVNI); 703 ErasedInstrs.insert(UseMI); 704 LIS->RemoveMachineInstrFromMaps(UseMI); 705 UseMI->eraseFromParent(); 706 } 707 708 // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition 709 // is updated. 710 VNInfo *ValNo = BValNo; 711 ValNo->def = AValNo->def; 712 for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 713 AI != AE; ++AI) { 714 if (AI->valno != AValNo) continue; 715 IntB.addRange(LiveRange(AI->start, AI->end, ValNo)); 716 } 717 DEBUG(dbgs() << "\t\textended: " << IntB << '\n'); 718 719 IntA.removeValNo(AValNo); 720 DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n'); 721 ++numCommutes; 722 return true; 723} 724 725/// reMaterializeTrivialDef - If the source of a copy is defined by a trivial 726/// computation, replace the copy by rematerialize the definition. 727bool RegisterCoalescer::reMaterializeTrivialDef(LiveInterval &SrcInt, 728 unsigned DstReg, 729 MachineInstr *CopyMI) { 730 SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(true); 731 LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx); 732 assert(SrcLR != SrcInt.end() && "Live range not found!"); 733 VNInfo *ValNo = SrcLR->valno; 734 if (ValNo->isPHIDef() || ValNo->isUnused()) 735 return false; 736 MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def); 737 if (!DefMI) 738 return false; 739 assert(DefMI && "Defining instruction disappeared"); 740 if (!DefMI->isAsCheapAsAMove()) 741 return false; 742 if (!TII->isTriviallyReMaterializable(DefMI, AA)) 743 return false; 744 bool SawStore = false; 745 if (!DefMI->isSafeToMove(TII, AA, SawStore)) 746 return false; 747 const MCInstrDesc &MCID = DefMI->getDesc(); 748 if (MCID.getNumDefs() != 1) 749 return false; 750 if (!DefMI->isImplicitDef()) { 751 // Make sure the copy destination register class fits the instruction 752 // definition register class. The mismatch can happen as a result of earlier 753 // extract_subreg, insert_subreg, subreg_to_reg coalescing. 754 const TargetRegisterClass *RC = TII->getRegClass(MCID, 0, TRI, *MF); 755 if (TargetRegisterInfo::isVirtualRegister(DstReg)) { 756 if (MRI->getRegClass(DstReg) != RC) 757 return false; 758 } else if (!RC->contains(DstReg)) 759 return false; 760 } 761 762 MachineBasicBlock *MBB = CopyMI->getParent(); 763 MachineBasicBlock::iterator MII = 764 llvm::next(MachineBasicBlock::iterator(CopyMI)); 765 TII->reMaterialize(*MBB, MII, DstReg, 0, DefMI, *TRI); 766 MachineInstr *NewMI = prior(MII); 767 768 // NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86). 769 // We need to remember these so we can add intervals once we insert 770 // NewMI into SlotIndexes. 771 SmallVector<unsigned, 4> NewMIImplDefs; 772 for (unsigned i = NewMI->getDesc().getNumOperands(), 773 e = NewMI->getNumOperands(); i != e; ++i) { 774 MachineOperand &MO = NewMI->getOperand(i); 775 if (MO.isReg()) { 776 assert(MO.isDef() && MO.isImplicit() && MO.isDead() && 777 TargetRegisterInfo::isPhysicalRegister(MO.getReg())); 778 NewMIImplDefs.push_back(MO.getReg()); 779 } 780 } 781 782 // CopyMI may have implicit operands, transfer them over to the newly 783 // rematerialized instruction. And update implicit def interval valnos. 784 for (unsigned i = CopyMI->getDesc().getNumOperands(), 785 e = CopyMI->getNumOperands(); i != e; ++i) { 786 MachineOperand &MO = CopyMI->getOperand(i); 787 if (MO.isReg()) { 788 assert(MO.isImplicit() && "No explicit operands after implict operands."); 789 // Discard VReg implicit defs. 790 if (TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { 791 NewMI->addOperand(MO); 792 } 793 } 794 } 795 796 LIS->ReplaceMachineInstrInMaps(CopyMI, NewMI); 797 798 SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI); 799 for (unsigned i = 0, e = NewMIImplDefs.size(); i != e; ++i) { 800 unsigned reg = NewMIImplDefs[i]; 801 LiveInterval &li = LIS->getInterval(reg); 802 VNInfo *DeadDefVN = li.getNextValue(NewMIIdx.getRegSlot(), 803 LIS->getVNInfoAllocator()); 804 LiveRange lr(NewMIIdx.getRegSlot(), NewMIIdx.getDeadSlot(), DeadDefVN); 805 li.addRange(lr); 806 } 807 808 CopyMI->eraseFromParent(); 809 ErasedInstrs.insert(CopyMI); 810 DEBUG(dbgs() << "Remat: " << *NewMI); 811 ++NumReMats; 812 813 // The source interval can become smaller because we removed a use. 814 LIS->shrinkToUses(&SrcInt, &DeadDefs); 815 if (!DeadDefs.empty()) 816 eliminateDeadDefs(); 817 818 return true; 819} 820 821/// eliminateUndefCopy - ProcessImpicitDefs may leave some copies of <undef> 822/// values, it only removes local variables. When we have a copy like: 823/// 824/// %vreg1 = COPY %vreg2<undef> 825/// 826/// We delete the copy and remove the corresponding value number from %vreg1. 827/// Any uses of that value number are marked as <undef>. 828bool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI, 829 const CoalescerPair &CP) { 830 SlotIndex Idx = LIS->getInstructionIndex(CopyMI); 831 LiveInterval *SrcInt = &LIS->getInterval(CP.getSrcReg()); 832 if (SrcInt->liveAt(Idx)) 833 return false; 834 LiveInterval *DstInt = &LIS->getInterval(CP.getDstReg()); 835 if (DstInt->liveAt(Idx)) 836 return false; 837 838 // No intervals are live-in to CopyMI - it is undef. 839 if (CP.isFlipped()) 840 DstInt = SrcInt; 841 SrcInt = 0; 842 843 VNInfo *DeadVNI = DstInt->getVNInfoAt(Idx.getRegSlot()); 844 assert(DeadVNI && "No value defined in DstInt"); 845 DstInt->removeValNo(DeadVNI); 846 847 // Find new undef uses. 848 for (MachineRegisterInfo::reg_nodbg_iterator 849 I = MRI->reg_nodbg_begin(DstInt->reg), E = MRI->reg_nodbg_end(); 850 I != E; ++I) { 851 MachineOperand &MO = I.getOperand(); 852 if (MO.isDef() || MO.isUndef()) 853 continue; 854 MachineInstr *MI = MO.getParent(); 855 SlotIndex Idx = LIS->getInstructionIndex(MI); 856 if (DstInt->liveAt(Idx)) 857 continue; 858 MO.setIsUndef(true); 859 DEBUG(dbgs() << "\tnew undef: " << Idx << '\t' << *MI); 860 } 861 return true; 862} 863 864/// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 865/// update the subregister number if it is not zero. If DstReg is a 866/// physical register and the existing subregister number of the def / use 867/// being updated is not zero, make sure to set it to the correct physical 868/// subregister. 869void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg, 870 unsigned DstReg, 871 unsigned SubIdx) { 872 bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 873 LiveInterval &DstInt = LIS->getInterval(DstReg); 874 875 // Update LiveDebugVariables. 876 LDV->renameRegister(SrcReg, DstReg, SubIdx); 877 878 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(SrcReg); 879 MachineInstr *UseMI = I.skipInstruction();) { 880 SmallVector<unsigned,8> Ops; 881 bool Reads, Writes; 882 tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops); 883 884 // If SrcReg wasn't read, it may still be the case that DstReg is live-in 885 // because SrcReg is a sub-register. 886 if (!Reads && SubIdx) 887 Reads = DstInt.liveAt(LIS->getInstructionIndex(UseMI)); 888 889 // Replace SrcReg with DstReg in all UseMI operands. 890 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 891 MachineOperand &MO = UseMI->getOperand(Ops[i]); 892 893 // Adjust <undef> flags in case of sub-register joins. We don't want to 894 // turn a full def into a read-modify-write sub-register def and vice 895 // versa. 896 if (SubIdx && MO.isDef()) 897 MO.setIsUndef(!Reads); 898 899 if (DstIsPhys) 900 MO.substPhysReg(DstReg, *TRI); 901 else 902 MO.substVirtReg(DstReg, SubIdx, *TRI); 903 } 904 905 DEBUG({ 906 dbgs() << "\t\tupdated: "; 907 if (!UseMI->isDebugValue()) 908 dbgs() << LIS->getInstructionIndex(UseMI) << "\t"; 909 dbgs() << *UseMI; 910 }); 911 } 912} 913 914/// canJoinPhys - Return true if a copy involving a physreg should be joined. 915bool RegisterCoalescer::canJoinPhys(CoalescerPair &CP) { 916 /// Always join simple intervals that are defined by a single copy from a 917 /// reserved register. This doesn't increase register pressure, so it is 918 /// always beneficial. 919 if (!RegClassInfo.isReserved(CP.getDstReg())) { 920 DEBUG(dbgs() << "\tCan only merge into reserved registers.\n"); 921 return false; 922 } 923 924 LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg()); 925 if (CP.isFlipped() && JoinVInt.containsOneValue()) 926 return true; 927 928 DEBUG(dbgs() << "\tCannot join defs into reserved register.\n"); 929 return false; 930} 931 932/// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 933/// which are the src/dst of the copy instruction CopyMI. This returns true 934/// if the copy was successfully coalesced away. If it is not currently 935/// possible to coalesce this interval, but it may be possible if other 936/// things get coalesced, then it returns true by reference in 'Again'. 937bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { 938 939 Again = false; 940 DEBUG(dbgs() << LIS->getInstructionIndex(CopyMI) << '\t' << *CopyMI); 941 942 CoalescerPair CP(*TII, *TRI); 943 if (!CP.setRegisters(CopyMI)) { 944 DEBUG(dbgs() << "\tNot coalescable.\n"); 945 return false; 946 } 947 948 // Dead code elimination. This really should be handled by MachineDCE, but 949 // sometimes dead copies slip through, and we can't generate invalid live 950 // ranges. 951 if (!CP.isPhys() && CopyMI->allDefsAreDead()) { 952 DEBUG(dbgs() << "\tCopy is dead.\n"); 953 DeadDefs.push_back(CopyMI); 954 eliminateDeadDefs(); 955 return true; 956 } 957 958 // Eliminate undefs. 959 if (!CP.isPhys() && eliminateUndefCopy(CopyMI, CP)) { 960 DEBUG(dbgs() << "\tEliminated copy of <undef> value.\n"); 961 LIS->RemoveMachineInstrFromMaps(CopyMI); 962 CopyMI->eraseFromParent(); 963 return false; // Not coalescable. 964 } 965 966 // Coalesced copies are normally removed immediately, but transformations 967 // like removeCopyByCommutingDef() can inadvertently create identity copies. 968 // When that happens, just join the values and remove the copy. 969 if (CP.getSrcReg() == CP.getDstReg()) { 970 LiveInterval &LI = LIS->getInterval(CP.getSrcReg()); 971 DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n'); 972 LiveRangeQuery LRQ(LI, LIS->getInstructionIndex(CopyMI)); 973 if (VNInfo *DefVNI = LRQ.valueDefined()) { 974 VNInfo *ReadVNI = LRQ.valueIn(); 975 assert(ReadVNI && "No value before copy and no <undef> flag."); 976 assert(ReadVNI != DefVNI && "Cannot read and define the same value."); 977 LI.MergeValueNumberInto(DefVNI, ReadVNI); 978 DEBUG(dbgs() << "\tMerged values: " << LI << '\n'); 979 } 980 LIS->RemoveMachineInstrFromMaps(CopyMI); 981 CopyMI->eraseFromParent(); 982 return true; 983 } 984 985 // Enforce policies. 986 if (CP.isPhys()) { 987 DEBUG(dbgs() << "\tConsidering merging " << PrintReg(CP.getSrcReg(), TRI) 988 << " with " << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) 989 << '\n'); 990 if (!canJoinPhys(CP)) { 991 // Before giving up coalescing, if definition of source is defined by 992 // trivial computation, try rematerializing it. 993 if (!CP.isFlipped() && 994 reMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()), 995 CP.getDstReg(), CopyMI)) 996 return true; 997 return false; 998 } 999 } else { 1000 DEBUG({ 1001 dbgs() << "\tConsidering merging to " << CP.getNewRC()->getName() 1002 << " with "; 1003 if (CP.getDstIdx() && CP.getSrcIdx()) 1004 dbgs() << PrintReg(CP.getDstReg()) << " in " 1005 << TRI->getSubRegIndexName(CP.getDstIdx()) << " and " 1006 << PrintReg(CP.getSrcReg()) << " in " 1007 << TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n'; 1008 else 1009 dbgs() << PrintReg(CP.getSrcReg(), TRI) << " in " 1010 << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n'; 1011 }); 1012 1013 // When possible, let DstReg be the larger interval. 1014 if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).ranges.size() > 1015 LIS->getInterval(CP.getDstReg()).ranges.size()) 1016 CP.flip(); 1017 } 1018 1019 // Okay, attempt to join these two intervals. On failure, this returns false. 1020 // Otherwise, if one of the intervals being joined is a physreg, this method 1021 // always canonicalizes DstInt to be it. The output "SrcInt" will not have 1022 // been modified, so we can use this information below to update aliases. 1023 if (!joinIntervals(CP)) { 1024 // Coalescing failed. 1025 1026 // If definition of source is defined by trivial computation, try 1027 // rematerializing it. 1028 if (!CP.isFlipped() && 1029 reMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()), 1030 CP.getDstReg(), CopyMI)) 1031 return true; 1032 1033 // If we can eliminate the copy without merging the live ranges, do so now. 1034 if (!CP.isPartial() && !CP.isPhys()) { 1035 if (adjustCopiesBackFrom(CP, CopyMI) || 1036 removeCopyByCommutingDef(CP, CopyMI)) { 1037 LIS->RemoveMachineInstrFromMaps(CopyMI); 1038 CopyMI->eraseFromParent(); 1039 DEBUG(dbgs() << "\tTrivial!\n"); 1040 return true; 1041 } 1042 } 1043 1044 // Otherwise, we are unable to join the intervals. 1045 DEBUG(dbgs() << "\tInterference!\n"); 1046 Again = true; // May be possible to coalesce later. 1047 return false; 1048 } 1049 1050 // Coalescing to a virtual register that is of a sub-register class of the 1051 // other. Make sure the resulting register is set to the right register class. 1052 if (CP.isCrossClass()) { 1053 ++numCrossRCs; 1054 MRI->setRegClass(CP.getDstReg(), CP.getNewRC()); 1055 } 1056 1057 // Removing sub-register copies can ease the register class constraints. 1058 // Make sure we attempt to inflate the register class of DstReg. 1059 if (!CP.isPhys() && RegClassInfo.isProperSubClass(CP.getNewRC())) 1060 InflateRegs.push_back(CP.getDstReg()); 1061 1062 // CopyMI has been erased by joinIntervals at this point. Remove it from 1063 // ErasedInstrs since copyCoalesceWorkList() won't add a successful join back 1064 // to the work list. This keeps ErasedInstrs from growing needlessly. 1065 ErasedInstrs.erase(CopyMI); 1066 1067 // Rewrite all SrcReg operands to DstReg. 1068 // Also update DstReg operands to include DstIdx if it is set. 1069 if (CP.getDstIdx()) 1070 updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx()); 1071 updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx()); 1072 1073 // SrcReg is guaranteed to be the register whose live interval that is 1074 // being merged. 1075 LIS->removeInterval(CP.getSrcReg()); 1076 1077 // Update regalloc hint. 1078 TRI->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF); 1079 1080 DEBUG(dbgs() << "\tJoined. Result = " << PrintReg(CP.getDstReg(), TRI) 1081 << ' ' << LIS->getInterval(CP.getDstReg()) << '\n'); 1082 1083 ++numJoins; 1084 return true; 1085} 1086 1087/// Attempt joining with a reserved physreg. 1088bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) { 1089 assert(CP.isPhys() && "Must be a physreg copy"); 1090 assert(RegClassInfo.isReserved(CP.getDstReg()) && "Not a reserved register"); 1091 LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1092 DEBUG(dbgs() << "\t\tRHS = " << PrintReg(CP.getSrcReg()) << ' ' << RHS 1093 << '\n'); 1094 1095 assert(CP.isFlipped() && RHS.containsOneValue() && 1096 "Invalid join with reserved register"); 1097 1098 // Optimization for reserved registers like ESP. We can only merge with a 1099 // reserved physreg if RHS has a single value that is a copy of CP.DstReg(). 1100 // The live range of the reserved register will look like a set of dead defs 1101 // - we don't properly track the live range of reserved registers. 1102 1103 // Deny any overlapping intervals. This depends on all the reserved 1104 // register live ranges to look like dead defs. 1105 for (MCRegAliasIterator AS(CP.getDstReg(), TRI, true); AS.isValid(); ++AS) { 1106 if (!LIS->hasInterval(*AS)) { 1107 // Make sure at least DstReg itself exists before attempting a join. 1108 if (*AS == CP.getDstReg()) 1109 LIS->getOrCreateInterval(CP.getDstReg()); 1110 continue; 1111 } 1112 if (RHS.overlaps(LIS->getInterval(*AS))) { 1113 DEBUG(dbgs() << "\t\tInterference: " << PrintReg(*AS, TRI) << '\n'); 1114 return false; 1115 } 1116 } 1117 // Skip any value computations, we are not adding new values to the 1118 // reserved register. Also skip merging the live ranges, the reserved 1119 // register live range doesn't need to be accurate as long as all the 1120 // defs are there. 1121 1122 // We don't track kills for reserved registers. 1123 MRI->clearKillFlags(CP.getSrcReg()); 1124 1125 return true; 1126} 1127 1128/// ComputeUltimateVN - Assuming we are going to join two live intervals, 1129/// compute what the resultant value numbers for each value in the input two 1130/// ranges will be. This is complicated by copies between the two which can 1131/// and will commonly cause multiple value numbers to be merged into one. 1132/// 1133/// VN is the value number that we're trying to resolve. InstDefiningValue 1134/// keeps track of the new InstDefiningValue assignment for the result 1135/// LiveInterval. ThisFromOther/OtherFromThis are sets that keep track of 1136/// whether a value in this or other is a copy from the opposite set. 1137/// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have 1138/// already been assigned. 1139/// 1140/// ThisFromOther[x] - If x is defined as a copy from the other interval, this 1141/// contains the value number the copy is from. 1142/// 1143static unsigned ComputeUltimateVN(VNInfo *VNI, 1144 SmallVector<VNInfo*, 16> &NewVNInfo, 1145 DenseMap<VNInfo*, VNInfo*> &ThisFromOther, 1146 DenseMap<VNInfo*, VNInfo*> &OtherFromThis, 1147 SmallVector<int, 16> &ThisValNoAssignments, 1148 SmallVector<int, 16> &OtherValNoAssignments) { 1149 unsigned VN = VNI->id; 1150 1151 // If the VN has already been computed, just return it. 1152 if (ThisValNoAssignments[VN] >= 0) 1153 return ThisValNoAssignments[VN]; 1154 assert(ThisValNoAssignments[VN] != -2 && "Cyclic value numbers"); 1155 1156 // If this val is not a copy from the other val, then it must be a new value 1157 // number in the destination. 1158 DenseMap<VNInfo*, VNInfo*>::iterator I = ThisFromOther.find(VNI); 1159 if (I == ThisFromOther.end()) { 1160 NewVNInfo.push_back(VNI); 1161 return ThisValNoAssignments[VN] = NewVNInfo.size()-1; 1162 } 1163 VNInfo *OtherValNo = I->second; 1164 1165 // Otherwise, this *is* a copy from the RHS. If the other side has already 1166 // been computed, return it. 1167 if (OtherValNoAssignments[OtherValNo->id] >= 0) 1168 return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id]; 1169 1170 // Mark this value number as currently being computed, then ask what the 1171 // ultimate value # of the other value is. 1172 ThisValNoAssignments[VN] = -2; 1173 unsigned UltimateVN = 1174 ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther, 1175 OtherValNoAssignments, ThisValNoAssignments); 1176 return ThisValNoAssignments[VN] = UltimateVN; 1177} 1178 1179 1180// Find out if we have something like 1181// A = X 1182// B = X 1183// if so, we can pretend this is actually 1184// A = X 1185// B = A 1186// which allows us to coalesce A and B. 1187// VNI is the definition of B. LR is the life range of A that includes 1188// the slot just before B. If we return true, we add "B = X" to DupCopies. 1189// This implies that A dominates B. 1190static bool RegistersDefinedFromSameValue(LiveIntervals &li, 1191 const TargetRegisterInfo &tri, 1192 CoalescerPair &CP, 1193 VNInfo *VNI, 1194 VNInfo *OtherVNI, 1195 SmallVector<MachineInstr*, 8> &DupCopies) { 1196 // FIXME: This is very conservative. For example, we don't handle 1197 // physical registers. 1198 1199 MachineInstr *MI = li.getInstructionFromIndex(VNI->def); 1200 1201 if (!MI || !MI->isFullCopy() || CP.isPartial() || CP.isPhys()) 1202 return false; 1203 1204 unsigned Dst = MI->getOperand(0).getReg(); 1205 unsigned Src = MI->getOperand(1).getReg(); 1206 1207 if (!TargetRegisterInfo::isVirtualRegister(Src) || 1208 !TargetRegisterInfo::isVirtualRegister(Dst)) 1209 return false; 1210 1211 unsigned A = CP.getDstReg(); 1212 unsigned B = CP.getSrcReg(); 1213 1214 if (B == Dst) 1215 std::swap(A, B); 1216 assert(Dst == A); 1217 1218 const MachineInstr *OtherMI = li.getInstructionFromIndex(OtherVNI->def); 1219 1220 if (!OtherMI || !OtherMI->isFullCopy()) 1221 return false; 1222 1223 unsigned OtherDst = OtherMI->getOperand(0).getReg(); 1224 unsigned OtherSrc = OtherMI->getOperand(1).getReg(); 1225 1226 if (!TargetRegisterInfo::isVirtualRegister(OtherSrc) || 1227 !TargetRegisterInfo::isVirtualRegister(OtherDst)) 1228 return false; 1229 1230 assert(OtherDst == B); 1231 1232 if (Src != OtherSrc) 1233 return false; 1234 1235 // If the copies use two different value numbers of X, we cannot merge 1236 // A and B. 1237 LiveInterval &SrcInt = li.getInterval(Src); 1238 // getVNInfoBefore returns NULL for undef copies. In this case, the 1239 // optimization is still safe. 1240 if (SrcInt.getVNInfoBefore(OtherVNI->def) != SrcInt.getVNInfoBefore(VNI->def)) 1241 return false; 1242 1243 DupCopies.push_back(MI); 1244 1245 return true; 1246} 1247 1248/// joinIntervals - Attempt to join these two intervals. On failure, this 1249/// returns false. 1250bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) { 1251 // Handle physreg joins separately. 1252 if (CP.isPhys()) 1253 return joinReservedPhysReg(CP); 1254 1255 LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1256 DEBUG(dbgs() << "\t\tRHS = " << PrintReg(CP.getSrcReg()) << ' ' << RHS 1257 << '\n'); 1258 1259 // Compute the final value assignment, assuming that the live ranges can be 1260 // coalesced. 1261 SmallVector<int, 16> LHSValNoAssignments; 1262 SmallVector<int, 16> RHSValNoAssignments; 1263 DenseMap<VNInfo*, VNInfo*> LHSValsDefinedFromRHS; 1264 DenseMap<VNInfo*, VNInfo*> RHSValsDefinedFromLHS; 1265 SmallVector<VNInfo*, 16> NewVNInfo; 1266 1267 SmallVector<MachineInstr*, 8> DupCopies; 1268 SmallVector<MachineInstr*, 8> DeadCopies; 1269 1270 LiveInterval &LHS = LIS->getOrCreateInterval(CP.getDstReg()); 1271 DEBUG(dbgs() << "\t\tLHS = " << PrintReg(CP.getDstReg(), TRI) << ' ' << LHS 1272 << '\n'); 1273 1274 // Loop over the value numbers of the LHS, seeing if any are defined from 1275 // the RHS. 1276 for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); 1277 i != e; ++i) { 1278 VNInfo *VNI = *i; 1279 if (VNI->isUnused() || VNI->isPHIDef()) 1280 continue; 1281 MachineInstr *MI = LIS->getInstructionFromIndex(VNI->def); 1282 assert(MI && "Missing def"); 1283 if (!MI->isCopyLike()) // Src not defined by a copy? 1284 continue; 1285 1286 // Figure out the value # from the RHS. 1287 VNInfo *OtherVNI = RHS.getVNInfoBefore(VNI->def); 1288 // The copy could be to an aliased physreg. 1289 if (!OtherVNI) 1290 continue; 1291 1292 // DstReg is known to be a register in the LHS interval. If the src is 1293 // from the RHS interval, we can use its value #. 1294 if (CP.isCoalescable(MI)) 1295 DeadCopies.push_back(MI); 1296 else if (!RegistersDefinedFromSameValue(*LIS, *TRI, CP, VNI, OtherVNI, 1297 DupCopies)) 1298 continue; 1299 1300 LHSValsDefinedFromRHS[VNI] = OtherVNI; 1301 } 1302 1303 // Loop over the value numbers of the RHS, seeing if any are defined from 1304 // the LHS. 1305 for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); 1306 i != e; ++i) { 1307 VNInfo *VNI = *i; 1308 if (VNI->isUnused() || VNI->isPHIDef()) 1309 continue; 1310 MachineInstr *MI = LIS->getInstructionFromIndex(VNI->def); 1311 assert(MI && "Missing def"); 1312 if (!MI->isCopyLike()) // Src not defined by a copy? 1313 continue; 1314 1315 // Figure out the value # from the LHS. 1316 VNInfo *OtherVNI = LHS.getVNInfoBefore(VNI->def); 1317 // The copy could be to an aliased physreg. 1318 if (!OtherVNI) 1319 continue; 1320 1321 // DstReg is known to be a register in the RHS interval. If the src is 1322 // from the LHS interval, we can use its value #. 1323 if (CP.isCoalescable(MI)) 1324 DeadCopies.push_back(MI); 1325 else if (!RegistersDefinedFromSameValue(*LIS, *TRI, CP, VNI, OtherVNI, 1326 DupCopies)) 1327 continue; 1328 1329 RHSValsDefinedFromLHS[VNI] = OtherVNI; 1330 } 1331 1332 LHSValNoAssignments.resize(LHS.getNumValNums(), -1); 1333 RHSValNoAssignments.resize(RHS.getNumValNums(), -1); 1334 NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums()); 1335 1336 for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); 1337 i != e; ++i) { 1338 VNInfo *VNI = *i; 1339 unsigned VN = VNI->id; 1340 if (LHSValNoAssignments[VN] >= 0 || VNI->isUnused()) 1341 continue; 1342 ComputeUltimateVN(VNI, NewVNInfo, 1343 LHSValsDefinedFromRHS, RHSValsDefinedFromLHS, 1344 LHSValNoAssignments, RHSValNoAssignments); 1345 } 1346 for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); 1347 i != e; ++i) { 1348 VNInfo *VNI = *i; 1349 unsigned VN = VNI->id; 1350 if (RHSValNoAssignments[VN] >= 0 || VNI->isUnused()) 1351 continue; 1352 // If this value number isn't a copy from the LHS, it's a new number. 1353 if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) { 1354 NewVNInfo.push_back(VNI); 1355 RHSValNoAssignments[VN] = NewVNInfo.size()-1; 1356 continue; 1357 } 1358 1359 ComputeUltimateVN(VNI, NewVNInfo, 1360 RHSValsDefinedFromLHS, LHSValsDefinedFromRHS, 1361 RHSValNoAssignments, LHSValNoAssignments); 1362 } 1363 1364 // Armed with the mappings of LHS/RHS values to ultimate values, walk the 1365 // interval lists to see if these intervals are coalescable. 1366 LiveInterval::const_iterator I = LHS.begin(); 1367 LiveInterval::const_iterator IE = LHS.end(); 1368 LiveInterval::const_iterator J = RHS.begin(); 1369 LiveInterval::const_iterator JE = RHS.end(); 1370 1371 // Collect interval end points that will no longer be kills. 1372 SmallVector<MachineInstr*, 8> LHSOldKills; 1373 SmallVector<MachineInstr*, 8> RHSOldKills; 1374 1375 // Skip ahead until the first place of potential sharing. 1376 if (I != IE && J != JE) { 1377 if (I->start < J->start) { 1378 I = std::upper_bound(I, IE, J->start); 1379 if (I != LHS.begin()) --I; 1380 } else if (J->start < I->start) { 1381 J = std::upper_bound(J, JE, I->start); 1382 if (J != RHS.begin()) --J; 1383 } 1384 } 1385 1386 while (I != IE && J != JE) { 1387 // Determine if these two live ranges overlap. 1388 // If so, check value # info to determine if they are really different. 1389 if (I->end > J->start && J->end > I->start) { 1390 // If the live range overlap will map to the same value number in the 1391 // result liverange, we can still coalesce them. If not, we can't. 1392 if (LHSValNoAssignments[I->valno->id] != 1393 RHSValNoAssignments[J->valno->id]) 1394 return false; 1395 1396 // Extended live ranges should no longer be killed. 1397 if (!I->end.isBlock() && I->end < J->end) 1398 if (MachineInstr *MI = LIS->getInstructionFromIndex(I->end)) 1399 LHSOldKills.push_back(MI); 1400 if (!J->end.isBlock() && J->end < I->end) 1401 if (MachineInstr *MI = LIS->getInstructionFromIndex(J->end)) 1402 RHSOldKills.push_back(MI); 1403 } 1404 1405 if (I->end < J->end) 1406 ++I; 1407 else 1408 ++J; 1409 } 1410 1411 // Update kill info. Some live ranges are extended due to copy coalescing. 1412 for (DenseMap<VNInfo*, VNInfo*>::iterator I = LHSValsDefinedFromRHS.begin(), 1413 E = LHSValsDefinedFromRHS.end(); I != E; ++I) { 1414 VNInfo *VNI = I->first; 1415 unsigned LHSValID = LHSValNoAssignments[VNI->id]; 1416 if (VNI->hasPHIKill()) 1417 NewVNInfo[LHSValID]->setHasPHIKill(true); 1418 } 1419 1420 // Update kill info. Some live ranges are extended due to copy coalescing. 1421 for (DenseMap<VNInfo*, VNInfo*>::iterator I = RHSValsDefinedFromLHS.begin(), 1422 E = RHSValsDefinedFromLHS.end(); I != E; ++I) { 1423 VNInfo *VNI = I->first; 1424 unsigned RHSValID = RHSValNoAssignments[VNI->id]; 1425 if (VNI->hasPHIKill()) 1426 NewVNInfo[RHSValID]->setHasPHIKill(true); 1427 } 1428 1429 // Clear kill flags where live ranges are extended. 1430 while (!LHSOldKills.empty()) 1431 LHSOldKills.pop_back_val()->clearRegisterKills(LHS.reg, TRI); 1432 while (!RHSOldKills.empty()) 1433 RHSOldKills.pop_back_val()->clearRegisterKills(RHS.reg, TRI); 1434 1435 if (LHSValNoAssignments.empty()) 1436 LHSValNoAssignments.push_back(-1); 1437 if (RHSValNoAssignments.empty()) 1438 RHSValNoAssignments.push_back(-1); 1439 1440 // Now erase all the redundant copies. 1441 for (unsigned i = 0, e = DeadCopies.size(); i != e; ++i) { 1442 MachineInstr *MI = DeadCopies[i]; 1443 if (!ErasedInstrs.insert(MI)) 1444 continue; 1445 DEBUG(dbgs() << "\t\terased:\t" << LIS->getInstructionIndex(MI) 1446 << '\t' << *MI); 1447 LIS->RemoveMachineInstrFromMaps(MI); 1448 MI->eraseFromParent(); 1449 } 1450 1451 SmallVector<unsigned, 8> SourceRegisters; 1452 for (SmallVector<MachineInstr*, 8>::iterator I = DupCopies.begin(), 1453 E = DupCopies.end(); I != E; ++I) { 1454 MachineInstr *MI = *I; 1455 if (!ErasedInstrs.insert(MI)) 1456 continue; 1457 1458 // We have pretended that the assignment to B in 1459 // A = X 1460 // B = X 1461 // was actually a copy from A. Now that we decided to coalesce A and B, 1462 // transform the code into 1463 // A = X 1464 unsigned Src = MI->getOperand(1).getReg(); 1465 SourceRegisters.push_back(Src); 1466 LIS->RemoveMachineInstrFromMaps(MI); 1467 MI->eraseFromParent(); 1468 } 1469 1470 // If B = X was the last use of X in a liverange, we have to shrink it now 1471 // that B = X is gone. 1472 for (SmallVector<unsigned, 8>::iterator I = SourceRegisters.begin(), 1473 E = SourceRegisters.end(); I != E; ++I) { 1474 LIS->shrinkToUses(&LIS->getInterval(*I)); 1475 } 1476 1477 // If we get here, we know that we can coalesce the live ranges. Ask the 1478 // intervals to coalesce themselves now. 1479 LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo, 1480 MRI); 1481 return true; 1482} 1483 1484namespace { 1485 // DepthMBBCompare - Comparison predicate that sort first based on the loop 1486 // depth of the basic block (the unsigned), and then on the MBB number. 1487 struct DepthMBBCompare { 1488 typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair; 1489 bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { 1490 // Deeper loops first 1491 if (LHS.first != RHS.first) 1492 return LHS.first > RHS.first; 1493 1494 // Prefer blocks that are more connected in the CFG. This takes care of 1495 // the most difficult copies first while intervals are short. 1496 unsigned cl = LHS.second->pred_size() + LHS.second->succ_size(); 1497 unsigned cr = RHS.second->pred_size() + RHS.second->succ_size(); 1498 if (cl != cr) 1499 return cl > cr; 1500 1501 // As a last resort, sort by block number. 1502 return LHS.second->getNumber() < RHS.second->getNumber(); 1503 } 1504 }; 1505} 1506 1507// Try joining WorkList copies starting from index From. 1508// Null out any successful joins. 1509bool RegisterCoalescer::copyCoalesceWorkList(unsigned From) { 1510 assert(From <= WorkList.size() && "Out of range"); 1511 bool Progress = false; 1512 for (unsigned i = From, e = WorkList.size(); i != e; ++i) { 1513 if (!WorkList[i]) 1514 continue; 1515 // Skip instruction pointers that have already been erased, for example by 1516 // dead code elimination. 1517 if (ErasedInstrs.erase(WorkList[i])) { 1518 WorkList[i] = 0; 1519 continue; 1520 } 1521 bool Again = false; 1522 bool Success = joinCopy(WorkList[i], Again); 1523 Progress |= Success; 1524 if (Success || !Again) 1525 WorkList[i] = 0; 1526 } 1527 return Progress; 1528} 1529 1530void 1531RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) { 1532 DEBUG(dbgs() << MBB->getName() << ":\n"); 1533 1534 // Collect all copy-like instructions in MBB. Don't start coalescing anything 1535 // yet, it might invalidate the iterator. 1536 const unsigned PrevSize = WorkList.size(); 1537 for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 1538 MII != E; ++MII) 1539 if (MII->isCopyLike()) 1540 WorkList.push_back(MII); 1541 1542 // Try coalescing the collected copies immediately, and remove the nulls. 1543 // This prevents the WorkList from getting too large since most copies are 1544 // joinable on the first attempt. 1545 if (copyCoalesceWorkList(PrevSize)) 1546 WorkList.erase(std::remove(WorkList.begin() + PrevSize, WorkList.end(), 1547 (MachineInstr*)0), WorkList.end()); 1548} 1549 1550void RegisterCoalescer::joinAllIntervals() { 1551 DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n"); 1552 assert(WorkList.empty() && "Old data still around."); 1553 1554 if (Loops->empty()) { 1555 // If there are no loops in the function, join intervals in function order. 1556 for (MachineFunction::iterator I = MF->begin(), E = MF->end(); 1557 I != E; ++I) 1558 copyCoalesceInMBB(I); 1559 } else { 1560 // Otherwise, join intervals in inner loops before other intervals. 1561 // Unfortunately we can't just iterate over loop hierarchy here because 1562 // there may be more MBB's than BB's. Collect MBB's for sorting. 1563 1564 // Join intervals in the function prolog first. We want to join physical 1565 // registers with virtual registers before the intervals got too long. 1566 std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs; 1567 for (MachineFunction::iterator I = MF->begin(), E = MF->end();I != E;++I){ 1568 MachineBasicBlock *MBB = I; 1569 MBBs.push_back(std::make_pair(Loops->getLoopDepth(MBB), I)); 1570 } 1571 1572 // Sort by loop depth. 1573 std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); 1574 1575 // Finally, join intervals in loop nest order. 1576 for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 1577 copyCoalesceInMBB(MBBs[i].second); 1578 } 1579 1580 // Joining intervals can allow other intervals to be joined. Iteratively join 1581 // until we make no progress. 1582 while (copyCoalesceWorkList()) 1583 /* empty */ ; 1584} 1585 1586void RegisterCoalescer::releaseMemory() { 1587 ErasedInstrs.clear(); 1588 WorkList.clear(); 1589 DeadDefs.clear(); 1590 InflateRegs.clear(); 1591} 1592 1593bool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) { 1594 MF = &fn; 1595 MRI = &fn.getRegInfo(); 1596 TM = &fn.getTarget(); 1597 TRI = TM->getRegisterInfo(); 1598 TII = TM->getInstrInfo(); 1599 LIS = &getAnalysis<LiveIntervals>(); 1600 LDV = &getAnalysis<LiveDebugVariables>(); 1601 AA = &getAnalysis<AliasAnalysis>(); 1602 Loops = &getAnalysis<MachineLoopInfo>(); 1603 1604 DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n" 1605 << "********** Function: " 1606 << ((Value*)MF->getFunction())->getName() << '\n'); 1607 1608 if (VerifyCoalescing) 1609 MF->verify(this, "Before register coalescing"); 1610 1611 RegClassInfo.runOnMachineFunction(fn); 1612 1613 // Join (coalesce) intervals if requested. 1614 if (EnableJoining) 1615 joinAllIntervals(); 1616 1617 // After deleting a lot of copies, register classes may be less constrained. 1618 // Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 -> 1619 // DPR inflation. 1620 array_pod_sort(InflateRegs.begin(), InflateRegs.end()); 1621 InflateRegs.erase(std::unique(InflateRegs.begin(), InflateRegs.end()), 1622 InflateRegs.end()); 1623 DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size() << " regs.\n"); 1624 for (unsigned i = 0, e = InflateRegs.size(); i != e; ++i) { 1625 unsigned Reg = InflateRegs[i]; 1626 if (MRI->reg_nodbg_empty(Reg)) 1627 continue; 1628 if (MRI->recomputeRegClass(Reg, *TM)) { 1629 DEBUG(dbgs() << PrintReg(Reg) << " inflated to " 1630 << MRI->getRegClass(Reg)->getName() << '\n'); 1631 ++NumInflated; 1632 } 1633 } 1634 1635 DEBUG(dump()); 1636 DEBUG(LDV->dump()); 1637 if (VerifyCoalescing) 1638 MF->verify(this, "After register coalescing"); 1639 return true; 1640} 1641 1642/// print - Implement the dump method. 1643void RegisterCoalescer::print(raw_ostream &O, const Module* m) const { 1644 LIS->print(O, m); 1645} 1646