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