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