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