RegisterCoalescer.cpp revision 4991de8fe1e72230cf714378b96411f1b59f6b77
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 400 // Bail if there is no dst interval - can happen when merging physical subreg 401 // operations. 402 if (!LIS->hasInterval(CP.getDstReg())) 403 return false; 404 405 LiveInterval &IntA = 406 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 407 LiveInterval &IntB = 408 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 409 SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 410 411 // BValNo is a value number in B that is defined by a copy from A. 'B3' in 412 // the example above. 413 LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); 414 if (BLR == IntB.end()) return false; 415 VNInfo *BValNo = BLR->valno; 416 417 // Get the location that B is defined at. Two options: either this value has 418 // an unknown definition point or it is defined at CopyIdx. If unknown, we 419 // can't process it. 420 if (BValNo->def != CopyIdx) return false; 421 422 // AValNo is the value number in A that defines the copy, A3 in the example. 423 SlotIndex CopyUseIdx = CopyIdx.getRegSlot(true); 424 LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx); 425 // The live range might not exist after fun with physreg coalescing. 426 if (ALR == IntA.end()) return false; 427 VNInfo *AValNo = ALR->valno; 428 429 // If AValNo is defined as a copy from IntB, we can potentially process this. 430 // Get the instruction that defines this value number. 431 MachineInstr *ACopyMI = LIS->getInstructionFromIndex(AValNo->def); 432 if (!CP.isCoalescable(ACopyMI)) 433 return false; 434 435 // Get the LiveRange in IntB that this value number starts with. 436 LiveInterval::iterator ValLR = 437 IntB.FindLiveRangeContaining(AValNo->def.getPrevSlot()); 438 if (ValLR == IntB.end()) 439 return false; 440 441 // Make sure that the end of the live range is inside the same block as 442 // CopyMI. 443 MachineInstr *ValLREndInst = 444 LIS->getInstructionFromIndex(ValLR->end.getPrevSlot()); 445 if (!ValLREndInst || ValLREndInst->getParent() != CopyMI->getParent()) 446 return false; 447 448 // Okay, we now know that ValLR ends in the same block that the CopyMI 449 // live-range starts. If there are no intervening live ranges between them in 450 // IntB, we can merge them. 451 if (ValLR+1 != BLR) return false; 452 453 // If a live interval is a physical register, conservatively check if any 454 // of its aliases is overlapping the live interval of the virtual register. 455 // If so, do not coalesce. 456 if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) { 457 for (const uint16_t *AS = TRI->getAliasSet(IntB.reg); *AS; ++AS) 458 if (LIS->hasInterval(*AS) && IntA.overlaps(LIS->getInterval(*AS))) { 459 DEBUG({ 460 dbgs() << "\t\tInterfere with alias "; 461 LIS->getInterval(*AS).print(dbgs(), TRI); 462 }); 463 return false; 464 } 465 } 466 467 DEBUG({ 468 dbgs() << "Extending: "; 469 IntB.print(dbgs(), TRI); 470 }); 471 472 SlotIndex FillerStart = ValLR->end, FillerEnd = BLR->start; 473 // We are about to delete CopyMI, so need to remove it as the 'instruction 474 // that defines this value #'. Update the valnum with the new defining 475 // instruction #. 476 BValNo->def = FillerStart; 477 478 // Okay, we can merge them. We need to insert a new liverange: 479 // [ValLR.end, BLR.begin) of either value number, then we merge the 480 // two value numbers. 481 IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo)); 482 483 // If the IntB live range is assigned to a physical register, and if that 484 // physreg has sub-registers, update their live intervals as well. 485 if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) { 486 for (const uint16_t *SR = TRI->getSubRegisters(IntB.reg); *SR; ++SR) { 487 if (!LIS->hasInterval(*SR)) 488 continue; 489 LiveInterval &SRLI = LIS->getInterval(*SR); 490 SRLI.addRange(LiveRange(FillerStart, FillerEnd, 491 SRLI.getNextValue(FillerStart, 492 LIS->getVNInfoAllocator()))); 493 } 494 } 495 496 // Okay, merge "B1" into the same value number as "B0". 497 if (BValNo != ValLR->valno) { 498 // If B1 is killed by a PHI, then the merged live range must also be killed 499 // by the same PHI, as B0 and B1 can not overlap. 500 bool HasPHIKill = BValNo->hasPHIKill(); 501 IntB.MergeValueNumberInto(BValNo, ValLR->valno); 502 if (HasPHIKill) 503 ValLR->valno->setHasPHIKill(true); 504 } 505 DEBUG({ 506 dbgs() << " result = "; 507 IntB.print(dbgs(), TRI); 508 dbgs() << "\n"; 509 }); 510 511 // If the source instruction was killing the source register before the 512 // merge, unset the isKill marker given the live range has been extended. 513 int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true); 514 if (UIdx != -1) { 515 ValLREndInst->getOperand(UIdx).setIsKill(false); 516 } 517 518 // Rewrite the copy. If the copy instruction was killing the destination 519 // register before the merge, find the last use and trim the live range. That 520 // will also add the isKill marker. 521 CopyMI->substituteRegister(IntA.reg, IntB.reg, 0, *TRI); 522 if (ALR->end == CopyIdx) 523 LIS->shrinkToUses(&IntA); 524 525 ++numExtends; 526 return true; 527} 528 529/// hasOtherReachingDefs - Return true if there are definitions of IntB 530/// other than BValNo val# that can reach uses of AValno val# of IntA. 531bool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA, 532 LiveInterval &IntB, 533 VNInfo *AValNo, 534 VNInfo *BValNo) { 535 for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 536 AI != AE; ++AI) { 537 if (AI->valno != AValNo) continue; 538 LiveInterval::Ranges::iterator BI = 539 std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start); 540 if (BI != IntB.ranges.begin()) 541 --BI; 542 for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) { 543 if (BI->valno == BValNo) 544 continue; 545 if (BI->start <= AI->start && BI->end > AI->start) 546 return true; 547 if (BI->start > AI->start && BI->start < AI->end) 548 return true; 549 } 550 } 551 return false; 552} 553 554/// removeCopyByCommutingDef - We found a non-trivially-coalescable copy with 555/// IntA being the source and IntB being the dest, thus this defines a value 556/// number in IntB. If the source value number (in IntA) is defined by a 557/// commutable instruction and its other operand is coalesced to the copy dest 558/// register, see if we can transform the copy into a noop by commuting the 559/// definition. For example, 560/// 561/// A3 = op A2 B0<kill> 562/// ... 563/// B1 = A3 <- this copy 564/// ... 565/// = op A3 <- more uses 566/// 567/// ==> 568/// 569/// B2 = op B0 A2<kill> 570/// ... 571/// B1 = B2 <- now an identify copy 572/// ... 573/// = op B2 <- more uses 574/// 575/// This returns true if an interval was modified. 576/// 577bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, 578 MachineInstr *CopyMI) { 579 // FIXME: For now, only eliminate the copy by commuting its def when the 580 // source register is a virtual register. We want to guard against cases 581 // where the copy is a back edge copy and commuting the def lengthen the 582 // live interval of the source register to the entire loop. 583 if (CP.isPhys() && CP.isFlipped()) 584 return false; 585 586 // Bail if there is no dst interval. 587 if (!LIS->hasInterval(CP.getDstReg())) 588 return false; 589 590 SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 591 592 LiveInterval &IntA = 593 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 594 LiveInterval &IntB = 595 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 596 597 // BValNo is a value number in B that is defined by a copy from A. 'B3' in 598 // the example above. 599 VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx); 600 if (!BValNo || BValNo->def != CopyIdx) 601 return false; 602 603 assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); 604 605 // AValNo is the value number in A that defines the copy, A3 in the example. 606 VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true)); 607 assert(AValNo && "COPY source not live"); 608 609 // If other defs can reach uses of this def, then it's not safe to perform 610 // the optimization. 611 if (AValNo->isPHIDef() || AValNo->isUnused() || AValNo->hasPHIKill()) 612 return false; 613 MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def); 614 if (!DefMI) 615 return false; 616 if (!DefMI->isCommutable()) 617 return false; 618 // If DefMI is a two-address instruction then commuting it will change the 619 // destination register. 620 int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg); 621 assert(DefIdx != -1); 622 unsigned UseOpIdx; 623 if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx)) 624 return false; 625 unsigned Op1, Op2, NewDstIdx; 626 if (!TII->findCommutedOpIndices(DefMI, Op1, Op2)) 627 return false; 628 if (Op1 == UseOpIdx) 629 NewDstIdx = Op2; 630 else if (Op2 == UseOpIdx) 631 NewDstIdx = Op1; 632 else 633 return false; 634 635 MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); 636 unsigned NewReg = NewDstMO.getReg(); 637 if (NewReg != IntB.reg || !NewDstMO.isKill()) 638 return false; 639 640 // Make sure there are no other definitions of IntB that would reach the 641 // uses which the new definition can reach. 642 if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo)) 643 return false; 644 645 // Abort if the aliases of IntB.reg have values that are not simply the 646 // clobbers from the superreg. 647 if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) 648 for (const uint16_t *AS = TRI->getAliasSet(IntB.reg); *AS; ++AS) 649 if (LIS->hasInterval(*AS) && 650 hasOtherReachingDefs(IntA, LIS->getInterval(*AS), AValNo, 0)) 651 return false; 652 653 // If some of the uses of IntA.reg is already coalesced away, return false. 654 // It's not possible to determine whether it's safe to perform the coalescing. 655 for (MachineRegisterInfo::use_nodbg_iterator UI = 656 MRI->use_nodbg_begin(IntA.reg), 657 UE = MRI->use_nodbg_end(); UI != UE; ++UI) { 658 MachineInstr *UseMI = &*UI; 659 SlotIndex UseIdx = LIS->getInstructionIndex(UseMI); 660 LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 661 if (ULR == IntA.end() || ULR->valno != AValNo) 662 continue; 663 // If this use is tied to a def, we can't rewrite the register. 664 if (UseMI->isRegTiedToDefOperand(UI.getOperandNo())) 665 return false; 666 } 667 668 DEBUG(dbgs() << "\tremoveCopyByCommutingDef: " << AValNo->def << '\t' 669 << *DefMI); 670 671 // At this point we have decided that it is legal to do this 672 // transformation. Start by commuting the instruction. 673 MachineBasicBlock *MBB = DefMI->getParent(); 674 MachineInstr *NewMI = TII->commuteInstruction(DefMI); 675 if (!NewMI) 676 return false; 677 if (TargetRegisterInfo::isVirtualRegister(IntA.reg) && 678 TargetRegisterInfo::isVirtualRegister(IntB.reg) && 679 !MRI->constrainRegClass(IntB.reg, MRI->getRegClass(IntA.reg))) 680 return false; 681 if (NewMI != DefMI) { 682 LIS->ReplaceMachineInstrInMaps(DefMI, NewMI); 683 MachineBasicBlock::iterator Pos = DefMI; 684 MBB->insert(Pos, NewMI); 685 MBB->erase(DefMI); 686 } 687 unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false); 688 NewMI->getOperand(OpIdx).setIsKill(); 689 690 // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g. 691 // A = or A, B 692 // ... 693 // B = A 694 // ... 695 // C = A<kill> 696 // ... 697 // = B 698 699 // Update uses of IntA of the specific Val# with IntB. 700 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(IntA.reg), 701 UE = MRI->use_end(); UI != UE;) { 702 MachineOperand &UseMO = UI.getOperand(); 703 MachineInstr *UseMI = &*UI; 704 ++UI; 705 if (UseMI->isDebugValue()) { 706 // FIXME These don't have an instruction index. Not clear we have enough 707 // info to decide whether to do this replacement or not. For now do it. 708 UseMO.setReg(NewReg); 709 continue; 710 } 711 SlotIndex UseIdx = LIS->getInstructionIndex(UseMI).getRegSlot(true); 712 LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 713 if (ULR == IntA.end() || ULR->valno != AValNo) 714 continue; 715 if (TargetRegisterInfo::isPhysicalRegister(NewReg)) 716 UseMO.substPhysReg(NewReg, *TRI); 717 else 718 UseMO.setReg(NewReg); 719 if (UseMI == CopyMI) 720 continue; 721 if (!UseMI->isCopy()) 722 continue; 723 if (UseMI->getOperand(0).getReg() != IntB.reg || 724 UseMI->getOperand(0).getSubReg()) 725 continue; 726 727 // This copy will become a noop. If it's defining a new val#, merge it into 728 // BValNo. 729 SlotIndex DefIdx = UseIdx.getRegSlot(); 730 VNInfo *DVNI = IntB.getVNInfoAt(DefIdx); 731 if (!DVNI) 732 continue; 733 DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI); 734 assert(DVNI->def == DefIdx); 735 BValNo = IntB.MergeValueNumberInto(BValNo, DVNI); 736 ErasedInstrs.insert(UseMI); 737 LIS->RemoveMachineInstrFromMaps(UseMI); 738 UseMI->eraseFromParent(); 739 } 740 741 // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition 742 // is updated. 743 VNInfo *ValNo = BValNo; 744 ValNo->def = AValNo->def; 745 for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 746 AI != AE; ++AI) { 747 if (AI->valno != AValNo) continue; 748 IntB.addRange(LiveRange(AI->start, AI->end, ValNo)); 749 } 750 DEBUG(dbgs() << "\t\textended: " << IntB << '\n'); 751 752 IntA.removeValNo(AValNo); 753 DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n'); 754 ++numCommutes; 755 return true; 756} 757 758/// reMaterializeTrivialDef - If the source of a copy is defined by a trivial 759/// computation, replace the copy by rematerialize the definition. 760bool RegisterCoalescer::reMaterializeTrivialDef(LiveInterval &SrcInt, 761 unsigned DstReg, 762 MachineInstr *CopyMI) { 763 SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(true); 764 LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx); 765 assert(SrcLR != SrcInt.end() && "Live range not found!"); 766 VNInfo *ValNo = SrcLR->valno; 767 if (ValNo->isPHIDef() || ValNo->isUnused()) 768 return false; 769 MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def); 770 if (!DefMI) 771 return false; 772 assert(DefMI && "Defining instruction disappeared"); 773 if (!DefMI->isAsCheapAsAMove()) 774 return false; 775 if (!TII->isTriviallyReMaterializable(DefMI, AA)) 776 return false; 777 bool SawStore = false; 778 if (!DefMI->isSafeToMove(TII, AA, SawStore)) 779 return false; 780 const MCInstrDesc &MCID = DefMI->getDesc(); 781 if (MCID.getNumDefs() != 1) 782 return false; 783 if (!DefMI->isImplicitDef()) { 784 // Make sure the copy destination register class fits the instruction 785 // definition register class. The mismatch can happen as a result of earlier 786 // extract_subreg, insert_subreg, subreg_to_reg coalescing. 787 const TargetRegisterClass *RC = TII->getRegClass(MCID, 0, TRI, *MF); 788 if (TargetRegisterInfo::isVirtualRegister(DstReg)) { 789 if (MRI->getRegClass(DstReg) != RC) 790 return false; 791 } else if (!RC->contains(DstReg)) 792 return false; 793 } 794 795 MachineBasicBlock *MBB = CopyMI->getParent(); 796 MachineBasicBlock::iterator MII = 797 llvm::next(MachineBasicBlock::iterator(CopyMI)); 798 TII->reMaterialize(*MBB, MII, DstReg, 0, DefMI, *TRI); 799 MachineInstr *NewMI = prior(MII); 800 801 // NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86). 802 // We need to remember these so we can add intervals once we insert 803 // NewMI into SlotIndexes. 804 SmallVector<unsigned, 4> NewMIImplDefs; 805 for (unsigned i = NewMI->getDesc().getNumOperands(), 806 e = NewMI->getNumOperands(); i != e; ++i) { 807 MachineOperand &MO = NewMI->getOperand(i); 808 if (MO.isReg()) { 809 assert(MO.isDef() && MO.isImplicit() && MO.isDead() && 810 TargetRegisterInfo::isPhysicalRegister(MO.getReg())); 811 NewMIImplDefs.push_back(MO.getReg()); 812 } 813 } 814 815 // CopyMI may have implicit operands, transfer them over to the newly 816 // rematerialized instruction. And update implicit def interval valnos. 817 for (unsigned i = CopyMI->getDesc().getNumOperands(), 818 e = CopyMI->getNumOperands(); i != e; ++i) { 819 MachineOperand &MO = CopyMI->getOperand(i); 820 if (MO.isReg()) { 821 assert(MO.isImplicit() && "No explicit operands after implict operands."); 822 // Discard VReg implicit defs. 823 if (TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { 824 NewMI->addOperand(MO); 825 } 826 } 827 } 828 829 LIS->ReplaceMachineInstrInMaps(CopyMI, NewMI); 830 831 SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI); 832 for (unsigned i = 0, e = NewMIImplDefs.size(); i != e; ++i) { 833 unsigned reg = NewMIImplDefs[i]; 834 LiveInterval &li = LIS->getInterval(reg); 835 VNInfo *DeadDefVN = li.getNextValue(NewMIIdx.getRegSlot(), 836 LIS->getVNInfoAllocator()); 837 LiveRange lr(NewMIIdx.getRegSlot(), NewMIIdx.getDeadSlot(), DeadDefVN); 838 li.addRange(lr); 839 } 840 841 CopyMI->eraseFromParent(); 842 ErasedInstrs.insert(CopyMI); 843 DEBUG(dbgs() << "Remat: " << *NewMI); 844 ++NumReMats; 845 846 // The source interval can become smaller because we removed a use. 847 LIS->shrinkToUses(&SrcInt, &DeadDefs); 848 if (!DeadDefs.empty()) 849 eliminateDeadDefs(); 850 851 return true; 852} 853 854/// eliminateUndefCopy - ProcessImpicitDefs may leave some copies of <undef> 855/// values, it only removes local variables. When we have a copy like: 856/// 857/// %vreg1 = COPY %vreg2<undef> 858/// 859/// We delete the copy and remove the corresponding value number from %vreg1. 860/// Any uses of that value number are marked as <undef>. 861bool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI, 862 const CoalescerPair &CP) { 863 SlotIndex Idx = LIS->getInstructionIndex(CopyMI); 864 LiveInterval *SrcInt = &LIS->getInterval(CP.getSrcReg()); 865 if (SrcInt->liveAt(Idx)) 866 return false; 867 LiveInterval *DstInt = &LIS->getInterval(CP.getDstReg()); 868 if (DstInt->liveAt(Idx)) 869 return false; 870 871 // No intervals are live-in to CopyMI - it is undef. 872 if (CP.isFlipped()) 873 DstInt = SrcInt; 874 SrcInt = 0; 875 876 VNInfo *DeadVNI = DstInt->getVNInfoAt(Idx.getRegSlot()); 877 assert(DeadVNI && "No value defined in DstInt"); 878 DstInt->removeValNo(DeadVNI); 879 880 // Find new undef uses. 881 for (MachineRegisterInfo::reg_nodbg_iterator 882 I = MRI->reg_nodbg_begin(DstInt->reg), E = MRI->reg_nodbg_end(); 883 I != E; ++I) { 884 MachineOperand &MO = I.getOperand(); 885 if (MO.isDef() || MO.isUndef()) 886 continue; 887 MachineInstr *MI = MO.getParent(); 888 SlotIndex Idx = LIS->getInstructionIndex(MI); 889 if (DstInt->liveAt(Idx)) 890 continue; 891 MO.setIsUndef(true); 892 DEBUG(dbgs() << "\tnew undef: " << Idx << '\t' << *MI); 893 } 894 return true; 895} 896 897/// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 898/// update the subregister number if it is not zero. If DstReg is a 899/// physical register and the existing subregister number of the def / use 900/// being updated is not zero, make sure to set it to the correct physical 901/// subregister. 902void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg, 903 unsigned DstReg, 904 unsigned SubIdx) { 905 bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 906 LiveInterval &DstInt = LIS->getInterval(DstReg); 907 908 // Update LiveDebugVariables. 909 LDV->renameRegister(SrcReg, DstReg, SubIdx); 910 911 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(SrcReg); 912 MachineInstr *UseMI = I.skipInstruction();) { 913 SmallVector<unsigned,8> Ops; 914 bool Reads, Writes; 915 tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops); 916 917 // If SrcReg wasn't read, it may still be the case that DstReg is live-in 918 // because SrcReg is a sub-register. 919 if (!Reads && SubIdx) 920 Reads = DstInt.liveAt(LIS->getInstructionIndex(UseMI)); 921 922 // Replace SrcReg with DstReg in all UseMI operands. 923 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 924 MachineOperand &MO = UseMI->getOperand(Ops[i]); 925 926 // Adjust <undef> flags in case of sub-register joins. We don't want to 927 // turn a full def into a read-modify-write sub-register def and vice 928 // versa. 929 if (SubIdx && MO.isDef()) 930 MO.setIsUndef(!Reads); 931 932 if (DstIsPhys) 933 MO.substPhysReg(DstReg, *TRI); 934 else 935 MO.substVirtReg(DstReg, SubIdx, *TRI); 936 } 937 938 DEBUG({ 939 dbgs() << "\t\tupdated: "; 940 if (!UseMI->isDebugValue()) 941 dbgs() << LIS->getInstructionIndex(UseMI) << "\t"; 942 dbgs() << *UseMI; 943 }); 944 } 945} 946 947/// canJoinPhys - Return true if a copy involving a physreg should be joined. 948bool RegisterCoalescer::canJoinPhys(CoalescerPair &CP) { 949 /// Always join simple intervals that are defined by a single copy from a 950 /// reserved register. This doesn't increase register pressure, so it is 951 /// always beneficial. 952 if (!RegClassInfo.isReserved(CP.getDstReg())) { 953 DEBUG(dbgs() << "\tCan only merge into reserved registers.\n"); 954 return false; 955 } 956 957 LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg()); 958 if (CP.isFlipped() && JoinVInt.containsOneValue()) 959 return true; 960 961 DEBUG(dbgs() << "\tCannot join defs into reserved register.\n"); 962 return false; 963} 964 965/// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 966/// which are the src/dst of the copy instruction CopyMI. This returns true 967/// if the copy was successfully coalesced away. If it is not currently 968/// possible to coalesce this interval, but it may be possible if other 969/// things get coalesced, then it returns true by reference in 'Again'. 970bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { 971 972 Again = false; 973 DEBUG(dbgs() << LIS->getInstructionIndex(CopyMI) << '\t' << *CopyMI); 974 975 CoalescerPair CP(*TII, *TRI); 976 if (!CP.setRegisters(CopyMI)) { 977 DEBUG(dbgs() << "\tNot coalescable.\n"); 978 return false; 979 } 980 981 // Dead code elimination. This really should be handled by MachineDCE, but 982 // sometimes dead copies slip through, and we can't generate invalid live 983 // ranges. 984 if (!CP.isPhys() && CopyMI->allDefsAreDead()) { 985 DEBUG(dbgs() << "\tCopy is dead.\n"); 986 DeadDefs.push_back(CopyMI); 987 eliminateDeadDefs(); 988 return true; 989 } 990 991 // If they are already joined we continue. 992 if (CP.getSrcReg() == CP.getDstReg()) { 993 DEBUG(dbgs() << "\tCopy already coalesced.\n"); 994 LIS->RemoveMachineInstrFromMaps(CopyMI); 995 CopyMI->eraseFromParent(); 996 return false; // Not coalescable. 997 } 998 999 // Eliminate undefs. 1000 if (!CP.isPhys() && eliminateUndefCopy(CopyMI, CP)) { 1001 DEBUG(dbgs() << "\tEliminated copy of <undef> value.\n"); 1002 LIS->RemoveMachineInstrFromMaps(CopyMI); 1003 CopyMI->eraseFromParent(); 1004 return false; // Not coalescable. 1005 } 1006 1007 // Enforce policies. 1008 if (CP.isPhys()) { 1009 DEBUG(dbgs() << "\tConsidering merging " << PrintReg(CP.getSrcReg(), TRI) 1010 << " with " << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) 1011 << '\n'); 1012 if (!canJoinPhys(CP)) { 1013 // Before giving up coalescing, if definition of source is defined by 1014 // trivial computation, try rematerializing it. 1015 if (!CP.isFlipped() && 1016 reMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()), 1017 CP.getDstReg(), CopyMI)) 1018 return true; 1019 return false; 1020 } 1021 } else { 1022 DEBUG({ 1023 dbgs() << "\tConsidering merging to " << CP.getNewRC()->getName() 1024 << " with "; 1025 if (CP.getDstIdx() && CP.getSrcIdx()) 1026 dbgs() << PrintReg(CP.getDstReg()) << " in " 1027 << TRI->getSubRegIndexName(CP.getDstIdx()) << " and " 1028 << PrintReg(CP.getSrcReg()) << " in " 1029 << TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n'; 1030 else 1031 dbgs() << PrintReg(CP.getSrcReg(), TRI) << " in " 1032 << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n'; 1033 }); 1034 1035 // When possible, let DstReg be the larger interval. 1036 if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).ranges.size() > 1037 LIS->getInterval(CP.getDstReg()).ranges.size()) 1038 CP.flip(); 1039 } 1040 1041 // Okay, attempt to join these two intervals. On failure, this returns false. 1042 // Otherwise, if one of the intervals being joined is a physreg, this method 1043 // always canonicalizes DstInt to be it. The output "SrcInt" will not have 1044 // been modified, so we can use this information below to update aliases. 1045 if (!joinIntervals(CP)) { 1046 // Coalescing failed. 1047 1048 // If definition of source is defined by trivial computation, try 1049 // rematerializing it. 1050 if (!CP.isFlipped() && 1051 reMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()), 1052 CP.getDstReg(), CopyMI)) 1053 return true; 1054 1055 // If we can eliminate the copy without merging the live ranges, do so now. 1056 if (!CP.isPartial()) { 1057 if (adjustCopiesBackFrom(CP, CopyMI) || 1058 removeCopyByCommutingDef(CP, CopyMI)) { 1059 LIS->RemoveMachineInstrFromMaps(CopyMI); 1060 CopyMI->eraseFromParent(); 1061 DEBUG(dbgs() << "\tTrivial!\n"); 1062 return true; 1063 } 1064 } 1065 1066 // Otherwise, we are unable to join the intervals. 1067 DEBUG(dbgs() << "\tInterference!\n"); 1068 Again = true; // May be possible to coalesce later. 1069 return false; 1070 } 1071 1072 // Coalescing to a virtual register that is of a sub-register class of the 1073 // other. Make sure the resulting register is set to the right register class. 1074 if (CP.isCrossClass()) { 1075 ++numCrossRCs; 1076 MRI->setRegClass(CP.getDstReg(), CP.getNewRC()); 1077 } 1078 1079 // Removing sub-register copies can ease the register class constraints. 1080 // Make sure we attempt to inflate the register class of DstReg. 1081 if (!CP.isPhys() && RegClassInfo.isProperSubClass(CP.getNewRC())) 1082 InflateRegs.push_back(CP.getDstReg()); 1083 1084 // CopyMI has been erased by joinIntervals at this point. Remove it from 1085 // ErasedInstrs since copyCoalesceWorkList() won't add a successful join back 1086 // to the work list. This keeps ErasedInstrs from growing needlessly. 1087 ErasedInstrs.erase(CopyMI); 1088 1089 // Rewrite all SrcReg operands to DstReg. 1090 // Also update DstReg operands to include DstIdx if it is set. 1091 if (CP.getDstIdx()) 1092 updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx()); 1093 updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx()); 1094 1095 // SrcReg is guaranteed to be the register whose live interval that is 1096 // being merged. 1097 LIS->removeInterval(CP.getSrcReg()); 1098 1099 // Update regalloc hint. 1100 TRI->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF); 1101 1102 DEBUG({ 1103 LiveInterval &DstInt = LIS->getInterval(CP.getDstReg()); 1104 dbgs() << "\tJoined. Result = "; 1105 DstInt.print(dbgs(), TRI); 1106 dbgs() << "\n"; 1107 }); 1108 1109 ++numJoins; 1110 return true; 1111} 1112 1113/// Attempt joining with a reserved physreg. 1114bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) { 1115 assert(CP.isPhys() && "Must be a physreg copy"); 1116 assert(RegClassInfo.isReserved(CP.getDstReg()) && "Not a reserved register"); 1117 LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1118 DEBUG({ dbgs() << "\t\tRHS = "; RHS.print(dbgs(), TRI); dbgs() << "\n"; }); 1119 1120 assert(CP.isFlipped() && RHS.containsOneValue() && 1121 "Invalid join with reserved register"); 1122 1123 // Optimization for reserved registers like ESP. We can only merge with a 1124 // reserved physreg if RHS has a single value that is a copy of CP.DstReg(). 1125 // The live range of the reserved register will look like a set of dead defs 1126 // - we don't properly track the live range of reserved registers. 1127 1128 // Deny any overlapping intervals. This depends on all the reserved 1129 // register live ranges to look like dead defs. 1130 for (const uint16_t *AS = TRI->getOverlaps(CP.getDstReg()); *AS; ++AS) { 1131 if (!LIS->hasInterval(*AS)) { 1132 // Make sure at least DstReg itself exists before attempting a join. 1133 if (*AS == CP.getDstReg()) 1134 LIS->getOrCreateInterval(CP.getDstReg()); 1135 continue; 1136 } 1137 if (RHS.overlaps(LIS->getInterval(*AS))) { 1138 DEBUG(dbgs() << "\t\tInterference: " << PrintReg(*AS, TRI) << '\n'); 1139 return false; 1140 } 1141 } 1142 // Skip any value computations, we are not adding new values to the 1143 // reserved register. Also skip merging the live ranges, the reserved 1144 // register live range doesn't need to be accurate as long as all the 1145 // defs are there. 1146 return true; 1147} 1148 1149/// ComputeUltimateVN - Assuming we are going to join two live intervals, 1150/// compute what the resultant value numbers for each value in the input two 1151/// ranges will be. This is complicated by copies between the two which can 1152/// and will commonly cause multiple value numbers to be merged into one. 1153/// 1154/// VN is the value number that we're trying to resolve. InstDefiningValue 1155/// keeps track of the new InstDefiningValue assignment for the result 1156/// LiveInterval. ThisFromOther/OtherFromThis are sets that keep track of 1157/// whether a value in this or other is a copy from the opposite set. 1158/// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have 1159/// already been assigned. 1160/// 1161/// ThisFromOther[x] - If x is defined as a copy from the other interval, this 1162/// contains the value number the copy is from. 1163/// 1164static unsigned ComputeUltimateVN(VNInfo *VNI, 1165 SmallVector<VNInfo*, 16> &NewVNInfo, 1166 DenseMap<VNInfo*, VNInfo*> &ThisFromOther, 1167 DenseMap<VNInfo*, VNInfo*> &OtherFromThis, 1168 SmallVector<int, 16> &ThisValNoAssignments, 1169 SmallVector<int, 16> &OtherValNoAssignments) { 1170 unsigned VN = VNI->id; 1171 1172 // If the VN has already been computed, just return it. 1173 if (ThisValNoAssignments[VN] >= 0) 1174 return ThisValNoAssignments[VN]; 1175 assert(ThisValNoAssignments[VN] != -2 && "Cyclic value numbers"); 1176 1177 // If this val is not a copy from the other val, then it must be a new value 1178 // number in the destination. 1179 DenseMap<VNInfo*, VNInfo*>::iterator I = ThisFromOther.find(VNI); 1180 if (I == ThisFromOther.end()) { 1181 NewVNInfo.push_back(VNI); 1182 return ThisValNoAssignments[VN] = NewVNInfo.size()-1; 1183 } 1184 VNInfo *OtherValNo = I->second; 1185 1186 // Otherwise, this *is* a copy from the RHS. If the other side has already 1187 // been computed, return it. 1188 if (OtherValNoAssignments[OtherValNo->id] >= 0) 1189 return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id]; 1190 1191 // Mark this value number as currently being computed, then ask what the 1192 // ultimate value # of the other value is. 1193 ThisValNoAssignments[VN] = -2; 1194 unsigned UltimateVN = 1195 ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther, 1196 OtherValNoAssignments, ThisValNoAssignments); 1197 return ThisValNoAssignments[VN] = UltimateVN; 1198} 1199 1200 1201// Find out if we have something like 1202// A = X 1203// B = X 1204// if so, we can pretend this is actually 1205// A = X 1206// B = A 1207// which allows us to coalesce A and B. 1208// VNI is the definition of B. LR is the life range of A that includes 1209// the slot just before B. If we return true, we add "B = X" to DupCopies. 1210// This implies that A dominates B. 1211static bool RegistersDefinedFromSameValue(LiveIntervals &li, 1212 const TargetRegisterInfo &tri, 1213 CoalescerPair &CP, 1214 VNInfo *VNI, 1215 VNInfo *OtherVNI, 1216 SmallVector<MachineInstr*, 8> &DupCopies) { 1217 // FIXME: This is very conservative. For example, we don't handle 1218 // physical registers. 1219 1220 MachineInstr *MI = li.getInstructionFromIndex(VNI->def); 1221 1222 if (!MI || !MI->isFullCopy() || CP.isPartial() || CP.isPhys()) 1223 return false; 1224 1225 unsigned Dst = MI->getOperand(0).getReg(); 1226 unsigned Src = MI->getOperand(1).getReg(); 1227 1228 if (!TargetRegisterInfo::isVirtualRegister(Src) || 1229 !TargetRegisterInfo::isVirtualRegister(Dst)) 1230 return false; 1231 1232 unsigned A = CP.getDstReg(); 1233 unsigned B = CP.getSrcReg(); 1234 1235 if (B == Dst) 1236 std::swap(A, B); 1237 assert(Dst == A); 1238 1239 const MachineInstr *OtherMI = li.getInstructionFromIndex(OtherVNI->def); 1240 1241 if (!OtherMI || !OtherMI->isFullCopy()) 1242 return false; 1243 1244 unsigned OtherDst = OtherMI->getOperand(0).getReg(); 1245 unsigned OtherSrc = OtherMI->getOperand(1).getReg(); 1246 1247 if (!TargetRegisterInfo::isVirtualRegister(OtherSrc) || 1248 !TargetRegisterInfo::isVirtualRegister(OtherDst)) 1249 return false; 1250 1251 assert(OtherDst == B); 1252 1253 if (Src != OtherSrc) 1254 return false; 1255 1256 // If the copies use two different value numbers of X, we cannot merge 1257 // A and B. 1258 LiveInterval &SrcInt = li.getInterval(Src); 1259 // getVNInfoBefore returns NULL for undef copies. In this case, the 1260 // optimization is still safe. 1261 if (SrcInt.getVNInfoBefore(OtherVNI->def) != SrcInt.getVNInfoBefore(VNI->def)) 1262 return false; 1263 1264 DupCopies.push_back(MI); 1265 1266 return true; 1267} 1268 1269/// joinIntervals - Attempt to join these two intervals. On failure, this 1270/// returns false. 1271bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) { 1272 // Handle physreg joins separately. 1273 if (CP.isPhys()) 1274 return joinReservedPhysReg(CP); 1275 1276 LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1277 DEBUG({ dbgs() << "\t\tRHS = "; RHS.print(dbgs(), TRI); dbgs() << "\n"; }); 1278 1279 // Compute the final value assignment, assuming that the live ranges can be 1280 // coalesced. 1281 SmallVector<int, 16> LHSValNoAssignments; 1282 SmallVector<int, 16> RHSValNoAssignments; 1283 DenseMap<VNInfo*, VNInfo*> LHSValsDefinedFromRHS; 1284 DenseMap<VNInfo*, VNInfo*> RHSValsDefinedFromLHS; 1285 SmallVector<VNInfo*, 16> NewVNInfo; 1286 1287 SmallVector<MachineInstr*, 8> DupCopies; 1288 SmallVector<MachineInstr*, 8> DeadCopies; 1289 1290 LiveInterval &LHS = LIS->getOrCreateInterval(CP.getDstReg()); 1291 DEBUG({ dbgs() << "\t\tLHS = "; LHS.print(dbgs(), TRI); dbgs() << "\n"; }); 1292 1293 // Loop over the value numbers of the LHS, seeing if any are defined from 1294 // the RHS. 1295 for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); 1296 i != e; ++i) { 1297 VNInfo *VNI = *i; 1298 if (VNI->isUnused() || VNI->isPHIDef()) 1299 continue; 1300 MachineInstr *MI = LIS->getInstructionFromIndex(VNI->def); 1301 assert(MI && "Missing def"); 1302 if (!MI->isCopyLike()) // Src not defined by a copy? 1303 continue; 1304 1305 // Figure out the value # from the RHS. 1306 VNInfo *OtherVNI = RHS.getVNInfoBefore(VNI->def); 1307 // The copy could be to an aliased physreg. 1308 if (!OtherVNI) 1309 continue; 1310 1311 // DstReg is known to be a register in the LHS interval. If the src is 1312 // from the RHS interval, we can use its value #. 1313 if (CP.isCoalescable(MI)) 1314 DeadCopies.push_back(MI); 1315 else if (!RegistersDefinedFromSameValue(*LIS, *TRI, CP, VNI, OtherVNI, 1316 DupCopies)) 1317 continue; 1318 1319 LHSValsDefinedFromRHS[VNI] = OtherVNI; 1320 } 1321 1322 // Loop over the value numbers of the RHS, seeing if any are defined from 1323 // the LHS. 1324 for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); 1325 i != e; ++i) { 1326 VNInfo *VNI = *i; 1327 if (VNI->isUnused() || VNI->isPHIDef()) 1328 continue; 1329 MachineInstr *MI = LIS->getInstructionFromIndex(VNI->def); 1330 assert(MI && "Missing def"); 1331 if (!MI->isCopyLike()) // Src not defined by a copy? 1332 continue; 1333 1334 // Figure out the value # from the LHS. 1335 VNInfo *OtherVNI = LHS.getVNInfoBefore(VNI->def); 1336 // The copy could be to an aliased physreg. 1337 if (!OtherVNI) 1338 continue; 1339 1340 // DstReg is known to be a register in the RHS interval. If the src is 1341 // from the LHS interval, we can use its value #. 1342 if (CP.isCoalescable(MI)) 1343 DeadCopies.push_back(MI); 1344 else if (!RegistersDefinedFromSameValue(*LIS, *TRI, CP, VNI, OtherVNI, 1345 DupCopies)) 1346 continue; 1347 1348 RHSValsDefinedFromLHS[VNI] = OtherVNI; 1349 } 1350 1351 LHSValNoAssignments.resize(LHS.getNumValNums(), -1); 1352 RHSValNoAssignments.resize(RHS.getNumValNums(), -1); 1353 NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums()); 1354 1355 for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); 1356 i != e; ++i) { 1357 VNInfo *VNI = *i; 1358 unsigned VN = VNI->id; 1359 if (LHSValNoAssignments[VN] >= 0 || VNI->isUnused()) 1360 continue; 1361 ComputeUltimateVN(VNI, NewVNInfo, 1362 LHSValsDefinedFromRHS, RHSValsDefinedFromLHS, 1363 LHSValNoAssignments, RHSValNoAssignments); 1364 } 1365 for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); 1366 i != e; ++i) { 1367 VNInfo *VNI = *i; 1368 unsigned VN = VNI->id; 1369 if (RHSValNoAssignments[VN] >= 0 || VNI->isUnused()) 1370 continue; 1371 // If this value number isn't a copy from the LHS, it's a new number. 1372 if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) { 1373 NewVNInfo.push_back(VNI); 1374 RHSValNoAssignments[VN] = NewVNInfo.size()-1; 1375 continue; 1376 } 1377 1378 ComputeUltimateVN(VNI, NewVNInfo, 1379 RHSValsDefinedFromLHS, LHSValsDefinedFromRHS, 1380 RHSValNoAssignments, LHSValNoAssignments); 1381 } 1382 1383 // Armed with the mappings of LHS/RHS values to ultimate values, walk the 1384 // interval lists to see if these intervals are coalescable. 1385 LiveInterval::const_iterator I = LHS.begin(); 1386 LiveInterval::const_iterator IE = LHS.end(); 1387 LiveInterval::const_iterator J = RHS.begin(); 1388 LiveInterval::const_iterator JE = RHS.end(); 1389 1390 // Skip ahead until the first place of potential sharing. 1391 if (I != IE && J != JE) { 1392 if (I->start < J->start) { 1393 I = std::upper_bound(I, IE, J->start); 1394 if (I != LHS.begin()) --I; 1395 } else if (J->start < I->start) { 1396 J = std::upper_bound(J, JE, I->start); 1397 if (J != RHS.begin()) --J; 1398 } 1399 } 1400 1401 while (I != IE && J != JE) { 1402 // Determine if these two live ranges overlap. 1403 // If so, check value # info to determine if they are really different. 1404 if (I->end > J->start && J->end > I->start) { 1405 // If the live range overlap will map to the same value number in the 1406 // result liverange, we can still coalesce them. If not, we can't. 1407 if (LHSValNoAssignments[I->valno->id] != 1408 RHSValNoAssignments[J->valno->id]) 1409 return false; 1410 } 1411 1412 if (I->end < J->end) 1413 ++I; 1414 else 1415 ++J; 1416 } 1417 1418 // Update kill info. Some live ranges are extended due to copy coalescing. 1419 for (DenseMap<VNInfo*, VNInfo*>::iterator I = LHSValsDefinedFromRHS.begin(), 1420 E = LHSValsDefinedFromRHS.end(); I != E; ++I) { 1421 VNInfo *VNI = I->first; 1422 unsigned LHSValID = LHSValNoAssignments[VNI->id]; 1423 if (VNI->hasPHIKill()) 1424 NewVNInfo[LHSValID]->setHasPHIKill(true); 1425 } 1426 1427 // Update kill info. Some live ranges are extended due to copy coalescing. 1428 for (DenseMap<VNInfo*, VNInfo*>::iterator I = RHSValsDefinedFromLHS.begin(), 1429 E = RHSValsDefinedFromLHS.end(); I != E; ++I) { 1430 VNInfo *VNI = I->first; 1431 unsigned RHSValID = RHSValNoAssignments[VNI->id]; 1432 if (VNI->hasPHIKill()) 1433 NewVNInfo[RHSValID]->setHasPHIKill(true); 1434 } 1435 1436 if (LHSValNoAssignments.empty()) 1437 LHSValNoAssignments.push_back(-1); 1438 if (RHSValNoAssignments.empty()) 1439 RHSValNoAssignments.push_back(-1); 1440 1441 // Now erase all the redundant copies. 1442 for (unsigned i = 0, e = DeadCopies.size(); i != e; ++i) { 1443 MachineInstr *MI = DeadCopies[i]; 1444 if (!ErasedInstrs.insert(MI)) 1445 continue; 1446 DEBUG(dbgs() << "\t\terased:\t" << LIS->getInstructionIndex(MI) 1447 << '\t' << *MI); 1448 LIS->RemoveMachineInstrFromMaps(MI); 1449 MI->eraseFromParent(); 1450 } 1451 1452 SmallVector<unsigned, 8> SourceRegisters; 1453 for (SmallVector<MachineInstr*, 8>::iterator I = DupCopies.begin(), 1454 E = DupCopies.end(); I != E; ++I) { 1455 MachineInstr *MI = *I; 1456 if (!ErasedInstrs.insert(MI)) 1457 continue; 1458 1459 // We have pretended that the assignment to B in 1460 // A = X 1461 // B = X 1462 // was actually a copy from A. Now that we decided to coalesce A and B, 1463 // transform the code into 1464 // A = X 1465 unsigned Src = MI->getOperand(1).getReg(); 1466 SourceRegisters.push_back(Src); 1467 LIS->RemoveMachineInstrFromMaps(MI); 1468 MI->eraseFromParent(); 1469 } 1470 1471 // If B = X was the last use of X in a liverange, we have to shrink it now 1472 // that B = X is gone. 1473 for (SmallVector<unsigned, 8>::iterator I = SourceRegisters.begin(), 1474 E = SourceRegisters.end(); I != E; ++I) { 1475 LIS->shrinkToUses(&LIS->getInterval(*I)); 1476 } 1477 1478 // If we get here, we know that we can coalesce the live ranges. Ask the 1479 // intervals to coalesce themselves now. 1480 LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo, 1481 MRI); 1482 return true; 1483} 1484 1485namespace { 1486 // DepthMBBCompare - Comparison predicate that sort first based on the loop 1487 // depth of the basic block (the unsigned), and then on the MBB number. 1488 struct DepthMBBCompare { 1489 typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair; 1490 bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { 1491 // Deeper loops first 1492 if (LHS.first != RHS.first) 1493 return LHS.first > RHS.first; 1494 1495 // Prefer blocks that are more connected in the CFG. This takes care of 1496 // the most difficult copies first while intervals are short. 1497 unsigned cl = LHS.second->pred_size() + LHS.second->succ_size(); 1498 unsigned cr = RHS.second->pred_size() + RHS.second->succ_size(); 1499 if (cl != cr) 1500 return cl > cr; 1501 1502 // As a last resort, sort by block number. 1503 return LHS.second->getNumber() < RHS.second->getNumber(); 1504 } 1505 }; 1506} 1507 1508// Try joining WorkList copies starting from index From. 1509// Null out any successful joins. 1510bool RegisterCoalescer::copyCoalesceWorkList(unsigned From) { 1511 assert(From <= WorkList.size() && "Out of range"); 1512 bool Progress = false; 1513 for (unsigned i = From, e = WorkList.size(); i != e; ++i) { 1514 if (!WorkList[i]) 1515 continue; 1516 // Skip instruction pointers that have already been erased, for example by 1517 // dead code elimination. 1518 if (ErasedInstrs.erase(WorkList[i])) { 1519 WorkList[i] = 0; 1520 continue; 1521 } 1522 bool Again = false; 1523 bool Success = joinCopy(WorkList[i], Again); 1524 Progress |= Success; 1525 if (Success || !Again) 1526 WorkList[i] = 0; 1527 } 1528 return Progress; 1529} 1530 1531void 1532RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) { 1533 DEBUG(dbgs() << MBB->getName() << ":\n"); 1534 1535 // Collect all copy-like instructions in MBB. Don't start coalescing anything 1536 // yet, it might invalidate the iterator. 1537 const unsigned PrevSize = WorkList.size(); 1538 for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 1539 MII != E; ++MII) 1540 if (MII->isCopyLike()) 1541 WorkList.push_back(MII); 1542 1543 // Try coalescing the collected copies immediately, and remove the nulls. 1544 // This prevents the WorkList from getting too large since most copies are 1545 // joinable on the first attempt. 1546 if (copyCoalesceWorkList(PrevSize)) 1547 WorkList.erase(std::remove(WorkList.begin() + PrevSize, WorkList.end(), 1548 (MachineInstr*)0), WorkList.end()); 1549} 1550 1551void RegisterCoalescer::joinAllIntervals() { 1552 DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n"); 1553 assert(WorkList.empty() && "Old data still around."); 1554 1555 if (Loops->empty()) { 1556 // If there are no loops in the function, join intervals in function order. 1557 for (MachineFunction::iterator I = MF->begin(), E = MF->end(); 1558 I != E; ++I) 1559 copyCoalesceInMBB(I); 1560 } else { 1561 // Otherwise, join intervals in inner loops before other intervals. 1562 // Unfortunately we can't just iterate over loop hierarchy here because 1563 // there may be more MBB's than BB's. Collect MBB's for sorting. 1564 1565 // Join intervals in the function prolog first. We want to join physical 1566 // registers with virtual registers before the intervals got too long. 1567 std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs; 1568 for (MachineFunction::iterator I = MF->begin(), E = MF->end();I != E;++I){ 1569 MachineBasicBlock *MBB = I; 1570 MBBs.push_back(std::make_pair(Loops->getLoopDepth(MBB), I)); 1571 } 1572 1573 // Sort by loop depth. 1574 std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); 1575 1576 // Finally, join intervals in loop nest order. 1577 for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 1578 copyCoalesceInMBB(MBBs[i].second); 1579 } 1580 1581 // Joining intervals can allow other intervals to be joined. Iteratively join 1582 // until we make no progress. 1583 while (copyCoalesceWorkList()) 1584 /* empty */ ; 1585} 1586 1587void RegisterCoalescer::releaseMemory() { 1588 ErasedInstrs.clear(); 1589 WorkList.clear(); 1590 DeadDefs.clear(); 1591 InflateRegs.clear(); 1592} 1593 1594bool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) { 1595 MF = &fn; 1596 MRI = &fn.getRegInfo(); 1597 TM = &fn.getTarget(); 1598 TRI = TM->getRegisterInfo(); 1599 TII = TM->getInstrInfo(); 1600 LIS = &getAnalysis<LiveIntervals>(); 1601 LDV = &getAnalysis<LiveDebugVariables>(); 1602 AA = &getAnalysis<AliasAnalysis>(); 1603 Loops = &getAnalysis<MachineLoopInfo>(); 1604 1605 DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n" 1606 << "********** Function: " 1607 << ((Value*)MF->getFunction())->getName() << '\n'); 1608 1609 if (VerifyCoalescing) 1610 MF->verify(this, "Before register coalescing"); 1611 1612 RegClassInfo.runOnMachineFunction(fn); 1613 1614 // Join (coalesce) intervals if requested. 1615 if (EnableJoining) { 1616 joinAllIntervals(); 1617 DEBUG({ 1618 dbgs() << "********** INTERVALS POST JOINING **********\n"; 1619 for (LiveIntervals::iterator I = LIS->begin(), E = LIS->end(); 1620 I != E; ++I){ 1621 I->second->print(dbgs(), TRI); 1622 dbgs() << "\n"; 1623 } 1624 }); 1625 } 1626 1627 // Perform a final pass over the instructions and compute spill weights 1628 // and remove identity moves. 1629 SmallVector<unsigned, 4> DeadDefs; 1630 for (MachineFunction::iterator mbbi = MF->begin(), mbbe = MF->end(); 1631 mbbi != mbbe; ++mbbi) { 1632 MachineBasicBlock* mbb = mbbi; 1633 for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); 1634 mii != mie; ) { 1635 MachineInstr *MI = mii; 1636 1637 ++mii; 1638 1639 // Check for now unnecessary kill flags. 1640 if (LIS->isNotInMIMap(MI)) continue; 1641 SlotIndex DefIdx = LIS->getInstructionIndex(MI).getRegSlot(); 1642 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1643 MachineOperand &MO = MI->getOperand(i); 1644 if (!MO.isReg() || !MO.isKill()) continue; 1645 unsigned reg = MO.getReg(); 1646 if (!reg || !LIS->hasInterval(reg)) continue; 1647 if (!LIS->getInterval(reg).killedAt(DefIdx)) { 1648 MO.setIsKill(false); 1649 continue; 1650 } 1651 // When leaving a kill flag on a physreg, check if any subregs should 1652 // remain alive. 1653 if (!TargetRegisterInfo::isPhysicalRegister(reg)) 1654 continue; 1655 for (const uint16_t *SR = TRI->getSubRegisters(reg); 1656 unsigned S = *SR; ++SR) 1657 if (LIS->hasInterval(S) && LIS->getInterval(S).liveAt(DefIdx)) 1658 MI->addRegisterDefined(S, TRI); 1659 } 1660 } 1661 } 1662 1663 // After deleting a lot of copies, register classes may be less constrained. 1664 // Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 -> 1665 // DPR inflation. 1666 array_pod_sort(InflateRegs.begin(), InflateRegs.end()); 1667 InflateRegs.erase(std::unique(InflateRegs.begin(), InflateRegs.end()), 1668 InflateRegs.end()); 1669 DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size() << " regs.\n"); 1670 for (unsigned i = 0, e = InflateRegs.size(); i != e; ++i) { 1671 unsigned Reg = InflateRegs[i]; 1672 if (MRI->reg_nodbg_empty(Reg)) 1673 continue; 1674 if (MRI->recomputeRegClass(Reg, *TM)) { 1675 DEBUG(dbgs() << PrintReg(Reg) << " inflated to " 1676 << MRI->getRegClass(Reg)->getName() << '\n'); 1677 ++NumInflated; 1678 } 1679 } 1680 1681 DEBUG(dump()); 1682 DEBUG(LDV->dump()); 1683 if (VerifyCoalescing) 1684 MF->verify(this, "After register coalescing"); 1685 return true; 1686} 1687 1688/// print - Implement the dump method. 1689void RegisterCoalescer::print(raw_ostream &O, const Module* m) const { 1690 LIS->print(O, m); 1691} 1692