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