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