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