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