RegisterCoalescer.cpp revision 2d5558cbaecfcaea72b80a725417dde6ed80ee04
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 "llvm/ADT/OwningPtr.h" 19#include "llvm/ADT/STLExtras.h" 20#include "llvm/ADT/SmallSet.h" 21#include "llvm/ADT/Statistic.h" 22#include "llvm/Analysis/AliasAnalysis.h" 23#include "llvm/CodeGen/LiveIntervalAnalysis.h" 24#include "llvm/CodeGen/LiveRangeEdit.h" 25#include "llvm/CodeGen/MachineFrameInfo.h" 26#include "llvm/CodeGen/MachineInstr.h" 27#include "llvm/CodeGen/MachineLoopInfo.h" 28#include "llvm/CodeGen/MachineRegisterInfo.h" 29#include "llvm/CodeGen/Passes.h" 30#include "llvm/CodeGen/RegisterClassInfo.h" 31#include "llvm/CodeGen/VirtRegMap.h" 32#include "llvm/IR/Value.h" 33#include "llvm/Pass.h" 34#include "llvm/Support/CommandLine.h" 35#include "llvm/Support/Debug.h" 36#include "llvm/Support/ErrorHandling.h" 37#include "llvm/Support/raw_ostream.h" 38#include "llvm/Target/TargetInstrInfo.h" 39#include "llvm/Target/TargetMachine.h" 40#include "llvm/Target/TargetRegisterInfo.h" 41#include "llvm/Target/TargetSubtargetInfo.h" 42#include <algorithm> 43#include <cmath> 44using namespace llvm; 45 46STATISTIC(numJoins , "Number of interval joins performed"); 47STATISTIC(numCrossRCs , "Number of cross class joins performed"); 48STATISTIC(numCommutes , "Number of instruction commuting performed"); 49STATISTIC(numExtends , "Number of copies extended"); 50STATISTIC(NumReMats , "Number of instructions re-materialized"); 51STATISTIC(NumInflated , "Number of register classes inflated"); 52STATISTIC(NumLaneConflicts, "Number of dead lane conflicts tested"); 53STATISTIC(NumLaneResolves, "Number of dead lane conflicts resolved"); 54 55static cl::opt<bool> 56EnableJoining("join-liveintervals", 57 cl::desc("Coalesce copies (default=true)"), 58 cl::init(true)); 59 60// Temporary flag to test critical edge unsplitting. 61static cl::opt<bool> 62EnableJoinSplits("join-splitedges", 63 cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden); 64 65// Temporary flag to test global copy optimization. 66static cl::opt<cl::boolOrDefault> 67EnableGlobalCopies("join-globalcopies", 68 cl::desc("Coalesce copies that span blocks (default=subtarget)"), 69 cl::init(cl::BOU_UNSET), cl::Hidden); 70 71static cl::opt<bool> 72VerifyCoalescing("verify-coalescing", 73 cl::desc("Verify machine instrs before and after register coalescing"), 74 cl::Hidden); 75 76namespace { 77 class RegisterCoalescer : public MachineFunctionPass, 78 private LiveRangeEdit::Delegate { 79 MachineFunction* MF; 80 MachineRegisterInfo* MRI; 81 const TargetMachine* TM; 82 const TargetRegisterInfo* TRI; 83 const TargetInstrInfo* TII; 84 LiveIntervals *LIS; 85 const MachineLoopInfo* Loops; 86 AliasAnalysis *AA; 87 RegisterClassInfo RegClassInfo; 88 89 /// \brief True if the coalescer should aggressively coalesce global copies 90 /// in favor of keeping local copies. 91 bool JoinGlobalCopies; 92 93 /// \brief True if the coalescer should aggressively coalesce fall-thru 94 /// blocks exclusively containing copies. 95 bool JoinSplitEdges; 96 97 /// WorkList - Copy instructions yet to be coalesced. 98 SmallVector<MachineInstr*, 8> WorkList; 99 SmallVector<MachineInstr*, 8> LocalWorkList; 100 101 /// ErasedInstrs - Set of instruction pointers that have been erased, and 102 /// that may be present in WorkList. 103 SmallPtrSet<MachineInstr*, 8> ErasedInstrs; 104 105 /// Dead instructions that are about to be deleted. 106 SmallVector<MachineInstr*, 8> DeadDefs; 107 108 /// Virtual registers to be considered for register class inflation. 109 SmallVector<unsigned, 8> InflateRegs; 110 111 /// Recursively eliminate dead defs in DeadDefs. 112 void eliminateDeadDefs(); 113 114 /// LiveRangeEdit callback. 115 void LRE_WillEraseInstruction(MachineInstr *MI); 116 117 /// coalesceLocals - coalesce the LocalWorkList. 118 void coalesceLocals(); 119 120 /// joinAllIntervals - join compatible live intervals 121 void joinAllIntervals(); 122 123 /// copyCoalesceInMBB - Coalesce copies in the specified MBB, putting 124 /// copies that cannot yet be coalesced into WorkList. 125 void copyCoalesceInMBB(MachineBasicBlock *MBB); 126 127 /// copyCoalesceWorkList - Try to coalesce all copies in CurrList. Return 128 /// true if any progress was made. 129 bool copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList); 130 131 /// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 132 /// which are the src/dst of the copy instruction CopyMI. This returns 133 /// true if the copy was successfully coalesced away. If it is not 134 /// currently possible to coalesce this interval, but it may be possible if 135 /// other things get coalesced, then it returns true by reference in 136 /// 'Again'. 137 bool joinCopy(MachineInstr *TheCopy, bool &Again); 138 139 /// joinIntervals - Attempt to join these two intervals. On failure, this 140 /// returns false. The output "SrcInt" will not have been modified, so we 141 /// can use this information below to update aliases. 142 bool joinIntervals(CoalescerPair &CP); 143 144 /// Attempt joining two virtual registers. Return true on success. 145 bool joinVirtRegs(CoalescerPair &CP); 146 147 /// Attempt joining with a reserved physreg. 148 bool joinReservedPhysReg(CoalescerPair &CP); 149 150 /// adjustCopiesBackFrom - We found a non-trivially-coalescable copy. If 151 /// the source value number is defined by a copy from the destination reg 152 /// see if we can merge these two destination reg valno# into a single 153 /// value number, eliminating a copy. 154 bool adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI); 155 156 /// hasOtherReachingDefs - Return true if there are definitions of IntB 157 /// other than BValNo val# that can reach uses of AValno val# of IntA. 158 bool hasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB, 159 VNInfo *AValNo, VNInfo *BValNo); 160 161 /// removeCopyByCommutingDef - We found a non-trivially-coalescable copy. 162 /// If the source value number is defined by a commutable instruction and 163 /// its other operand is coalesced to the copy dest register, see if we 164 /// can transform the copy into a noop by commuting the definition. 165 bool removeCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI); 166 167 /// reMaterializeTrivialDef - If the source of a copy is defined by a 168 /// trivial computation, replace the copy by rematerialize the definition. 169 bool reMaterializeTrivialDef(CoalescerPair &CP, MachineInstr *CopyMI, 170 bool &IsDefCopy); 171 172 /// canJoinPhys - Return true if a physreg copy should be joined. 173 bool canJoinPhys(const CoalescerPair &CP); 174 175 /// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 176 /// update the subregister number if it is not zero. If DstReg is a 177 /// physical register and the existing subregister number of the def / use 178 /// being updated is not zero, make sure to set it to the correct physical 179 /// subregister. 180 void updateRegDefsUses(unsigned SrcReg, unsigned DstReg, unsigned SubIdx); 181 182 /// eliminateUndefCopy - Handle copies of undef values. 183 bool eliminateUndefCopy(MachineInstr *CopyMI, const CoalescerPair &CP); 184 185 public: 186 static char ID; // Class identification, replacement for typeinfo 187 RegisterCoalescer() : MachineFunctionPass(ID) { 188 initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 189 } 190 191 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 192 193 virtual void releaseMemory(); 194 195 /// runOnMachineFunction - pass entry point 196 virtual bool runOnMachineFunction(MachineFunction&); 197 198 /// print - Implement the dump method. 199 virtual void print(raw_ostream &O, const Module* = 0) const; 200 }; 201} /// end anonymous namespace 202 203char &llvm::RegisterCoalescerID = RegisterCoalescer::ID; 204 205INITIALIZE_PASS_BEGIN(RegisterCoalescer, "simple-register-coalescing", 206 "Simple Register Coalescing", false, false) 207INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 208INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 209INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 210INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 211INITIALIZE_PASS_END(RegisterCoalescer, "simple-register-coalescing", 212 "Simple Register Coalescing", false, false) 213 214char RegisterCoalescer::ID = 0; 215 216static bool isMoveInstr(const TargetRegisterInfo &tri, const MachineInstr *MI, 217 unsigned &Src, unsigned &Dst, 218 unsigned &SrcSub, unsigned &DstSub) { 219 if (MI->isCopy()) { 220 Dst = MI->getOperand(0).getReg(); 221 DstSub = MI->getOperand(0).getSubReg(); 222 Src = MI->getOperand(1).getReg(); 223 SrcSub = MI->getOperand(1).getSubReg(); 224 } else if (MI->isSubregToReg()) { 225 Dst = MI->getOperand(0).getReg(); 226 DstSub = tri.composeSubRegIndices(MI->getOperand(0).getSubReg(), 227 MI->getOperand(3).getImm()); 228 Src = MI->getOperand(2).getReg(); 229 SrcSub = MI->getOperand(2).getSubReg(); 230 } else 231 return false; 232 return true; 233} 234 235// Return true if this block should be vacated by the coalescer to eliminate 236// branches. The important cases to handle in the coalescer are critical edges 237// split during phi elimination which contain only copies. Simple blocks that 238// contain non-branches should also be vacated, but this can be handled by an 239// earlier pass similar to early if-conversion. 240static bool isSplitEdge(const MachineBasicBlock *MBB) { 241 if (MBB->pred_size() != 1 || MBB->succ_size() != 1) 242 return false; 243 244 for (MachineBasicBlock::const_iterator MII = MBB->begin(), E = MBB->end(); 245 MII != E; ++MII) { 246 if (!MII->isCopyLike() && !MII->isUnconditionalBranch()) 247 return false; 248 } 249 return true; 250} 251 252bool CoalescerPair::setRegisters(const MachineInstr *MI) { 253 SrcReg = DstReg = 0; 254 SrcIdx = DstIdx = 0; 255 NewRC = 0; 256 Flipped = CrossClass = false; 257 258 unsigned Src, Dst, SrcSub, DstSub; 259 if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 260 return false; 261 Partial = SrcSub || DstSub; 262 263 // If one register is a physreg, it must be Dst. 264 if (TargetRegisterInfo::isPhysicalRegister(Src)) { 265 if (TargetRegisterInfo::isPhysicalRegister(Dst)) 266 return false; 267 std::swap(Src, Dst); 268 std::swap(SrcSub, DstSub); 269 Flipped = true; 270 } 271 272 const MachineRegisterInfo &MRI = MI->getParent()->getParent()->getRegInfo(); 273 274 if (TargetRegisterInfo::isPhysicalRegister(Dst)) { 275 // Eliminate DstSub on a physreg. 276 if (DstSub) { 277 Dst = TRI.getSubReg(Dst, DstSub); 278 if (!Dst) return false; 279 DstSub = 0; 280 } 281 282 // Eliminate SrcSub by picking a corresponding Dst superregister. 283 if (SrcSub) { 284 Dst = TRI.getMatchingSuperReg(Dst, SrcSub, MRI.getRegClass(Src)); 285 if (!Dst) return false; 286 SrcSub = 0; 287 } else if (!MRI.getRegClass(Src)->contains(Dst)) { 288 return false; 289 } 290 } else { 291 // Both registers are virtual. 292 const TargetRegisterClass *SrcRC = MRI.getRegClass(Src); 293 const TargetRegisterClass *DstRC = MRI.getRegClass(Dst); 294 295 // Both registers have subreg indices. 296 if (SrcSub && DstSub) { 297 // Copies between different sub-registers are never coalescable. 298 if (Src == Dst && SrcSub != DstSub) 299 return false; 300 301 NewRC = TRI.getCommonSuperRegClass(SrcRC, SrcSub, DstRC, DstSub, 302 SrcIdx, DstIdx); 303 if (!NewRC) 304 return false; 305 } else if (DstSub) { 306 // SrcReg will be merged with a sub-register of DstReg. 307 SrcIdx = DstSub; 308 NewRC = TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub); 309 } else if (SrcSub) { 310 // DstReg will be merged with a sub-register of SrcReg. 311 DstIdx = SrcSub; 312 NewRC = TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSub); 313 } else { 314 // This is a straight copy without sub-registers. 315 NewRC = TRI.getCommonSubClass(DstRC, SrcRC); 316 } 317 318 // The combined constraint may be impossible to satisfy. 319 if (!NewRC) 320 return false; 321 322 // Prefer SrcReg to be a sub-register of DstReg. 323 // FIXME: Coalescer should support subregs symmetrically. 324 if (DstIdx && !SrcIdx) { 325 std::swap(Src, Dst); 326 std::swap(SrcIdx, DstIdx); 327 Flipped = !Flipped; 328 } 329 330 CrossClass = NewRC != DstRC || NewRC != SrcRC; 331 } 332 // Check our invariants 333 assert(TargetRegisterInfo::isVirtualRegister(Src) && "Src must be virtual"); 334 assert(!(TargetRegisterInfo::isPhysicalRegister(Dst) && DstSub) && 335 "Cannot have a physical SubIdx"); 336 SrcReg = Src; 337 DstReg = Dst; 338 return true; 339} 340 341bool CoalescerPair::flip() { 342 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) 343 return false; 344 std::swap(SrcReg, DstReg); 345 std::swap(SrcIdx, DstIdx); 346 Flipped = !Flipped; 347 return true; 348} 349 350bool CoalescerPair::isCoalescable(const MachineInstr *MI) const { 351 if (!MI) 352 return false; 353 unsigned Src, Dst, SrcSub, DstSub; 354 if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 355 return false; 356 357 // Find the virtual register that is SrcReg. 358 if (Dst == SrcReg) { 359 std::swap(Src, Dst); 360 std::swap(SrcSub, DstSub); 361 } else if (Src != SrcReg) { 362 return false; 363 } 364 365 // Now check that Dst matches DstReg. 366 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { 367 if (!TargetRegisterInfo::isPhysicalRegister(Dst)) 368 return false; 369 assert(!DstIdx && !SrcIdx && "Inconsistent CoalescerPair state."); 370 // DstSub could be set for a physreg from INSERT_SUBREG. 371 if (DstSub) 372 Dst = TRI.getSubReg(Dst, DstSub); 373 // Full copy of Src. 374 if (!SrcSub) 375 return DstReg == Dst; 376 // This is a partial register copy. Check that the parts match. 377 return TRI.getSubReg(DstReg, SrcSub) == Dst; 378 } else { 379 // DstReg is virtual. 380 if (DstReg != Dst) 381 return false; 382 // Registers match, do the subregisters line up? 383 return TRI.composeSubRegIndices(SrcIdx, SrcSub) == 384 TRI.composeSubRegIndices(DstIdx, DstSub); 385 } 386} 387 388void RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const { 389 AU.setPreservesCFG(); 390 AU.addRequired<AliasAnalysis>(); 391 AU.addRequired<LiveIntervals>(); 392 AU.addPreserved<LiveIntervals>(); 393 AU.addPreserved<SlotIndexes>(); 394 AU.addRequired<MachineLoopInfo>(); 395 AU.addPreserved<MachineLoopInfo>(); 396 AU.addPreservedID(MachineDominatorsID); 397 MachineFunctionPass::getAnalysisUsage(AU); 398} 399 400void RegisterCoalescer::eliminateDeadDefs() { 401 SmallVector<unsigned, 8> NewRegs; 402 LiveRangeEdit(0, NewRegs, *MF, *LIS, 0, this).eliminateDeadDefs(DeadDefs); 403} 404 405// Callback from eliminateDeadDefs(). 406void RegisterCoalescer::LRE_WillEraseInstruction(MachineInstr *MI) { 407 // MI may be in WorkList. Make sure we don't visit it. 408 ErasedInstrs.insert(MI); 409} 410 411/// adjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA 412/// being the source and IntB being the dest, thus this defines a value number 413/// in IntB. If the source value number (in IntA) is defined by a copy from B, 414/// see if we can merge these two pieces of B into a single value number, 415/// eliminating a copy. For example: 416/// 417/// A3 = B0 418/// ... 419/// B1 = A3 <- this copy 420/// 421/// In this case, B0 can be extended to where the B1 copy lives, allowing the B1 422/// value number to be replaced with B0 (which simplifies the B liveinterval). 423/// 424/// This returns true if an interval was modified. 425/// 426bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP, 427 MachineInstr *CopyMI) { 428 assert(!CP.isPartial() && "This doesn't work for partial copies."); 429 assert(!CP.isPhys() && "This doesn't work for physreg copies."); 430 431 LiveInterval &IntA = 432 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 433 LiveInterval &IntB = 434 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 435 SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 436 437 // BValNo is a value number in B that is defined by a copy from A. 'B3' in 438 // the example above. 439 LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); 440 if (BLR == IntB.end()) return false; 441 VNInfo *BValNo = BLR->valno; 442 443 // Get the location that B is defined at. Two options: either this value has 444 // an unknown definition point or it is defined at CopyIdx. If unknown, we 445 // can't process it. 446 if (BValNo->def != CopyIdx) return false; 447 448 // AValNo is the value number in A that defines the copy, A3 in the example. 449 SlotIndex CopyUseIdx = CopyIdx.getRegSlot(true); 450 LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx); 451 // The live range might not exist after fun with physreg coalescing. 452 if (ALR == IntA.end()) return false; 453 VNInfo *AValNo = ALR->valno; 454 455 // If AValNo is defined as a copy from IntB, we can potentially process this. 456 // Get the instruction that defines this value number. 457 MachineInstr *ACopyMI = LIS->getInstructionFromIndex(AValNo->def); 458 // Don't allow any partial copies, even if isCoalescable() allows them. 459 if (!CP.isCoalescable(ACopyMI) || !ACopyMI->isFullCopy()) 460 return false; 461 462 // Get the LiveRange in IntB that this value number starts with. 463 LiveInterval::iterator ValLR = 464 IntB.FindLiveRangeContaining(AValNo->def.getPrevSlot()); 465 if (ValLR == IntB.end()) 466 return false; 467 468 // Make sure that the end of the live range is inside the same block as 469 // CopyMI. 470 MachineInstr *ValLREndInst = 471 LIS->getInstructionFromIndex(ValLR->end.getPrevSlot()); 472 if (!ValLREndInst || ValLREndInst->getParent() != CopyMI->getParent()) 473 return false; 474 475 // Okay, we now know that ValLR ends in the same block that the CopyMI 476 // live-range starts. If there are no intervening live ranges between them in 477 // IntB, we can merge them. 478 if (ValLR+1 != BLR) return false; 479 480 DEBUG(dbgs() << "Extending: " << PrintReg(IntB.reg, TRI)); 481 482 SlotIndex FillerStart = ValLR->end, FillerEnd = BLR->start; 483 // We are about to delete CopyMI, so need to remove it as the 'instruction 484 // that defines this value #'. Update the valnum with the new defining 485 // instruction #. 486 BValNo->def = FillerStart; 487 488 // Okay, we can merge them. We need to insert a new liverange: 489 // [ValLR.end, BLR.begin) of either value number, then we merge the 490 // two value numbers. 491 IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo)); 492 493 // Okay, merge "B1" into the same value number as "B0". 494 if (BValNo != ValLR->valno) 495 IntB.MergeValueNumberInto(BValNo, ValLR->valno); 496 DEBUG(dbgs() << " result = " << IntB << '\n'); 497 498 // If the source instruction was killing the source register before the 499 // merge, unset the isKill marker given the live range has been extended. 500 int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true); 501 if (UIdx != -1) { 502 ValLREndInst->getOperand(UIdx).setIsKill(false); 503 } 504 505 // Rewrite the copy. If the copy instruction was killing the destination 506 // register before the merge, find the last use and trim the live range. That 507 // will also add the isKill marker. 508 CopyMI->substituteRegister(IntA.reg, IntB.reg, 0, *TRI); 509 if (ALR->end == CopyIdx) 510 LIS->shrinkToUses(&IntA); 511 512 ++numExtends; 513 return true; 514} 515 516/// hasOtherReachingDefs - Return true if there are definitions of IntB 517/// other than BValNo val# that can reach uses of AValno val# of IntA. 518bool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA, 519 LiveInterval &IntB, 520 VNInfo *AValNo, 521 VNInfo *BValNo) { 522 // If AValNo has PHI kills, conservatively assume that IntB defs can reach 523 // the PHI values. 524 if (LIS->hasPHIKill(IntA, AValNo)) 525 return true; 526 527 for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 528 AI != AE; ++AI) { 529 if (AI->valno != AValNo) continue; 530 LiveInterval::Ranges::iterator BI = 531 std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start); 532 if (BI != IntB.ranges.begin()) 533 --BI; 534 for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) { 535 if (BI->valno == BValNo) 536 continue; 537 if (BI->start <= AI->start && BI->end > AI->start) 538 return true; 539 if (BI->start > AI->start && BI->start < AI->end) 540 return true; 541 } 542 } 543 return false; 544} 545 546/// removeCopyByCommutingDef - We found a non-trivially-coalescable copy with 547/// IntA being the source and IntB being the dest, thus this defines a value 548/// number in IntB. If the source value number (in IntA) is defined by a 549/// commutable instruction and its other operand is coalesced to the copy dest 550/// register, see if we can transform the copy into a noop by commuting the 551/// definition. For example, 552/// 553/// A3 = op A2 B0<kill> 554/// ... 555/// B1 = A3 <- this copy 556/// ... 557/// = op A3 <- more uses 558/// 559/// ==> 560/// 561/// B2 = op B0 A2<kill> 562/// ... 563/// B1 = B2 <- now an identify copy 564/// ... 565/// = op B2 <- more uses 566/// 567/// This returns true if an interval was modified. 568/// 569bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, 570 MachineInstr *CopyMI) { 571 assert (!CP.isPhys()); 572 573 SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 574 575 LiveInterval &IntA = 576 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 577 LiveInterval &IntB = 578 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 579 580 // BValNo is a value number in B that is defined by a copy from A. 'B1' in 581 // the example above. 582 VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx); 583 if (!BValNo || BValNo->def != CopyIdx) 584 return false; 585 586 // AValNo is the value number in A that defines the copy, A3 in the example. 587 VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true)); 588 assert(AValNo && "COPY source not live"); 589 if (AValNo->isPHIDef() || AValNo->isUnused()) 590 return false; 591 MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def); 592 if (!DefMI) 593 return false; 594 if (!DefMI->isCommutable()) 595 return false; 596 // If DefMI is a two-address instruction then commuting it will change the 597 // destination register. 598 int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg); 599 assert(DefIdx != -1); 600 unsigned UseOpIdx; 601 if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx)) 602 return false; 603 unsigned Op1, Op2, NewDstIdx; 604 if (!TII->findCommutedOpIndices(DefMI, Op1, Op2)) 605 return false; 606 if (Op1 == UseOpIdx) 607 NewDstIdx = Op2; 608 else if (Op2 == UseOpIdx) 609 NewDstIdx = Op1; 610 else 611 return false; 612 613 MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); 614 unsigned NewReg = NewDstMO.getReg(); 615 if (NewReg != IntB.reg || !LiveRangeQuery(IntB, AValNo->def).isKill()) 616 return false; 617 618 // Make sure there are no other definitions of IntB that would reach the 619 // uses which the new definition can reach. 620 if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo)) 621 return false; 622 623 // If some of the uses of IntA.reg is already coalesced away, return false. 624 // It's not possible to determine whether it's safe to perform the coalescing. 625 for (MachineRegisterInfo::use_nodbg_iterator UI = 626 MRI->use_nodbg_begin(IntA.reg), 627 UE = MRI->use_nodbg_end(); UI != UE; ++UI) { 628 MachineInstr *UseMI = &*UI; 629 SlotIndex UseIdx = LIS->getInstructionIndex(UseMI); 630 LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 631 if (ULR == IntA.end() || ULR->valno != AValNo) 632 continue; 633 // If this use is tied to a def, we can't rewrite the register. 634 if (UseMI->isRegTiedToDefOperand(UI.getOperandNo())) 635 return false; 636 } 637 638 DEBUG(dbgs() << "\tremoveCopyByCommutingDef: " << AValNo->def << '\t' 639 << *DefMI); 640 641 // At this point we have decided that it is legal to do this 642 // transformation. Start by commuting the instruction. 643 MachineBasicBlock *MBB = DefMI->getParent(); 644 MachineInstr *NewMI = TII->commuteInstruction(DefMI); 645 if (!NewMI) 646 return false; 647 if (TargetRegisterInfo::isVirtualRegister(IntA.reg) && 648 TargetRegisterInfo::isVirtualRegister(IntB.reg) && 649 !MRI->constrainRegClass(IntB.reg, MRI->getRegClass(IntA.reg))) 650 return false; 651 if (NewMI != DefMI) { 652 LIS->ReplaceMachineInstrInMaps(DefMI, NewMI); 653 MachineBasicBlock::iterator Pos = DefMI; 654 MBB->insert(Pos, NewMI); 655 MBB->erase(DefMI); 656 } 657 unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false); 658 NewMI->getOperand(OpIdx).setIsKill(); 659 660 // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g. 661 // A = or A, B 662 // ... 663 // B = A 664 // ... 665 // C = A<kill> 666 // ... 667 // = B 668 669 // Update uses of IntA of the specific Val# with IntB. 670 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(IntA.reg), 671 UE = MRI->use_end(); UI != UE;) { 672 MachineOperand &UseMO = UI.getOperand(); 673 MachineInstr *UseMI = &*UI; 674 ++UI; 675 if (UseMI->isDebugValue()) { 676 // FIXME These don't have an instruction index. Not clear we have enough 677 // info to decide whether to do this replacement or not. For now do it. 678 UseMO.setReg(NewReg); 679 continue; 680 } 681 SlotIndex UseIdx = LIS->getInstructionIndex(UseMI).getRegSlot(true); 682 LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 683 if (ULR == IntA.end() || ULR->valno != AValNo) 684 continue; 685 // Kill flags are no longer accurate. They are recomputed after RA. 686 UseMO.setIsKill(false); 687 if (TargetRegisterInfo::isPhysicalRegister(NewReg)) 688 UseMO.substPhysReg(NewReg, *TRI); 689 else 690 UseMO.setReg(NewReg); 691 if (UseMI == CopyMI) 692 continue; 693 if (!UseMI->isCopy()) 694 continue; 695 if (UseMI->getOperand(0).getReg() != IntB.reg || 696 UseMI->getOperand(0).getSubReg()) 697 continue; 698 699 // This copy will become a noop. If it's defining a new val#, merge it into 700 // BValNo. 701 SlotIndex DefIdx = UseIdx.getRegSlot(); 702 VNInfo *DVNI = IntB.getVNInfoAt(DefIdx); 703 if (!DVNI) 704 continue; 705 DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI); 706 assert(DVNI->def == DefIdx); 707 BValNo = IntB.MergeValueNumberInto(BValNo, DVNI); 708 ErasedInstrs.insert(UseMI); 709 LIS->RemoveMachineInstrFromMaps(UseMI); 710 UseMI->eraseFromParent(); 711 } 712 713 // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition 714 // is updated. 715 VNInfo *ValNo = BValNo; 716 ValNo->def = AValNo->def; 717 for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 718 AI != AE; ++AI) { 719 if (AI->valno != AValNo) continue; 720 IntB.addRange(LiveRange(AI->start, AI->end, ValNo)); 721 } 722 DEBUG(dbgs() << "\t\textended: " << IntB << '\n'); 723 724 IntA.removeValNo(AValNo); 725 DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n'); 726 ++numCommutes; 727 return true; 728} 729 730/// reMaterializeTrivialDef - If the source of a copy is defined by a trivial 731/// computation, replace the copy by rematerialize the definition. 732bool RegisterCoalescer::reMaterializeTrivialDef(CoalescerPair &CP, 733 MachineInstr *CopyMI, 734 bool &IsDefCopy) { 735 IsDefCopy = false; 736 unsigned SrcReg = CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg(); 737 unsigned SrcIdx = CP.isFlipped() ? CP.getDstIdx() : CP.getSrcIdx(); 738 unsigned DstReg = CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg(); 739 unsigned DstIdx = CP.isFlipped() ? CP.getSrcIdx() : CP.getDstIdx(); 740 if (TargetRegisterInfo::isPhysicalRegister(SrcReg)) 741 return false; 742 743 LiveInterval &SrcInt = LIS->getInterval(SrcReg); 744 SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI); 745 VNInfo *ValNo = LiveRangeQuery(SrcInt, CopyIdx).valueIn(); 746 assert(ValNo && "CopyMI input register not live"); 747 if (ValNo->isPHIDef() || ValNo->isUnused()) 748 return false; 749 MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def); 750 if (!DefMI) 751 return false; 752 if (DefMI->isCopyLike()) { 753 IsDefCopy = true; 754 return false; 755 } 756 if (!DefMI->isAsCheapAsAMove()) 757 return false; 758 if (!TII->isTriviallyReMaterializable(DefMI, AA)) 759 return false; 760 bool SawStore = false; 761 if (!DefMI->isSafeToMove(TII, AA, SawStore)) 762 return false; 763 const MCInstrDesc &MCID = DefMI->getDesc(); 764 if (MCID.getNumDefs() != 1) 765 return false; 766 // Only support subregister destinations when the def is read-undef. 767 MachineOperand &DstOperand = CopyMI->getOperand(0); 768 unsigned CopyDstReg = DstOperand.getReg(); 769 if (DstOperand.getSubReg() && !DstOperand.isUndef()) 770 return false; 771 772 const TargetRegisterClass *DefRC = TII->getRegClass(MCID, 0, TRI, *MF); 773 if (!DefMI->isImplicitDef()) { 774 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { 775 unsigned NewDstReg = DstReg; 776 777 unsigned NewDstIdx = TRI->composeSubRegIndices(CP.getSrcIdx(), 778 DefMI->getOperand(0).getSubReg()); 779 if (NewDstIdx) 780 NewDstReg = TRI->getSubReg(DstReg, NewDstIdx); 781 782 // Finally, make sure that the physical subregister that will be 783 // constructed later is permitted for the instruction. 784 if (!DefRC->contains(NewDstReg)) 785 return false; 786 } else { 787 // Theoretically, some stack frame reference could exist. Just make sure 788 // it hasn't actually happened. 789 assert(TargetRegisterInfo::isVirtualRegister(DstReg) && 790 "Only expect to deal with virtual or physical registers"); 791 } 792 } 793 794 MachineBasicBlock *MBB = CopyMI->getParent(); 795 MachineBasicBlock::iterator MII = 796 llvm::next(MachineBasicBlock::iterator(CopyMI)); 797 TII->reMaterialize(*MBB, MII, DstReg, SrcIdx, DefMI, *TRI); 798 MachineInstr *NewMI = prior(MII); 799 800 LIS->ReplaceMachineInstrInMaps(CopyMI, NewMI); 801 CopyMI->eraseFromParent(); 802 ErasedInstrs.insert(CopyMI); 803 804 // NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86). 805 // We need to remember these so we can add intervals once we insert 806 // NewMI into SlotIndexes. 807 SmallVector<unsigned, 4> NewMIImplDefs; 808 for (unsigned i = NewMI->getDesc().getNumOperands(), 809 e = NewMI->getNumOperands(); i != e; ++i) { 810 MachineOperand &MO = NewMI->getOperand(i); 811 if (MO.isReg()) { 812 assert(MO.isDef() && MO.isImplicit() && MO.isDead() && 813 TargetRegisterInfo::isPhysicalRegister(MO.getReg())); 814 NewMIImplDefs.push_back(MO.getReg()); 815 } 816 } 817 818 if (TargetRegisterInfo::isVirtualRegister(DstReg)) { 819 unsigned NewIdx = NewMI->getOperand(0).getSubReg(); 820 const TargetRegisterClass *RCForInst; 821 if (NewIdx) 822 RCForInst = TRI->getMatchingSuperRegClass(MRI->getRegClass(DstReg), DefRC, 823 NewIdx); 824 825 if (MRI->constrainRegClass(DstReg, DefRC)) { 826 // The materialized instruction is quite capable of setting DstReg 827 // directly, but it may still have a now-trivial subregister index which 828 // we should clear. 829 NewMI->getOperand(0).setSubReg(0); 830 } else if (NewIdx && RCForInst) { 831 // The subreg index on NewMI is essential; we still have to make sure 832 // DstReg:idx is in a class that NewMI can use. 833 MRI->constrainRegClass(DstReg, RCForInst); 834 } else { 835 // DstReg is actually incompatible with NewMI, we have to move to a 836 // super-reg's class. This could come from a sequence like: 837 // GR32 = MOV32r0 838 // GR8 = COPY GR32:sub_8 839 MRI->setRegClass(DstReg, CP.getNewRC()); 840 updateRegDefsUses(DstReg, DstReg, DstIdx); 841 NewMI->getOperand(0).setSubReg( 842 TRI->composeSubRegIndices(SrcIdx, DefMI->getOperand(0).getSubReg())); 843 } 844 } else if (NewMI->getOperand(0).getReg() != CopyDstReg) { 845 // The New instruction may be defining a sub-register of what's actually 846 // been asked for. If so it must implicitly define the whole thing. 847 assert(TargetRegisterInfo::isPhysicalRegister(DstReg) && 848 "Only expect virtual or physical registers in remat"); 849 NewMI->getOperand(0).setIsDead(true); 850 NewMI->addOperand(MachineOperand::CreateReg(CopyDstReg, 851 true /*IsDef*/, 852 true /*IsImp*/, 853 false /*IsKill*/)); 854 } 855 856 if (NewMI->getOperand(0).getSubReg()) 857 NewMI->getOperand(0).setIsUndef(); 858 859 // CopyMI may have implicit operands, transfer them over to the newly 860 // rematerialized instruction. And update implicit def interval valnos. 861 for (unsigned i = CopyMI->getDesc().getNumOperands(), 862 e = CopyMI->getNumOperands(); i != e; ++i) { 863 MachineOperand &MO = CopyMI->getOperand(i); 864 if (MO.isReg()) { 865 assert(MO.isImplicit() && "No explicit operands after implict operands."); 866 // Discard VReg implicit defs. 867 if (TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { 868 NewMI->addOperand(MO); 869 } 870 } 871 } 872 873 SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI); 874 for (unsigned i = 0, e = NewMIImplDefs.size(); i != e; ++i) { 875 unsigned Reg = NewMIImplDefs[i]; 876 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) 877 if (LiveInterval *LI = LIS->getCachedRegUnit(*Units)) 878 LI->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator()); 879 } 880 881 DEBUG(dbgs() << "Remat: " << *NewMI); 882 ++NumReMats; 883 884 // The source interval can become smaller because we removed a use. 885 LIS->shrinkToUses(&SrcInt, &DeadDefs); 886 if (!DeadDefs.empty()) 887 eliminateDeadDefs(); 888 889 return true; 890} 891 892/// eliminateUndefCopy - ProcessImpicitDefs may leave some copies of <undef> 893/// values, it only removes local variables. When we have a copy like: 894/// 895/// %vreg1 = COPY %vreg2<undef> 896/// 897/// We delete the copy and remove the corresponding value number from %vreg1. 898/// Any uses of that value number are marked as <undef>. 899bool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI, 900 const CoalescerPair &CP) { 901 SlotIndex Idx = LIS->getInstructionIndex(CopyMI); 902 LiveInterval *SrcInt = &LIS->getInterval(CP.getSrcReg()); 903 if (SrcInt->liveAt(Idx)) 904 return false; 905 LiveInterval *DstInt = &LIS->getInterval(CP.getDstReg()); 906 if (DstInt->liveAt(Idx)) 907 return false; 908 909 // No intervals are live-in to CopyMI - it is undef. 910 if (CP.isFlipped()) 911 DstInt = SrcInt; 912 SrcInt = 0; 913 914 VNInfo *DeadVNI = DstInt->getVNInfoAt(Idx.getRegSlot()); 915 assert(DeadVNI && "No value defined in DstInt"); 916 DstInt->removeValNo(DeadVNI); 917 918 // Find new undef uses. 919 for (MachineRegisterInfo::reg_nodbg_iterator 920 I = MRI->reg_nodbg_begin(DstInt->reg), E = MRI->reg_nodbg_end(); 921 I != E; ++I) { 922 MachineOperand &MO = I.getOperand(); 923 if (MO.isDef() || MO.isUndef()) 924 continue; 925 MachineInstr *MI = MO.getParent(); 926 SlotIndex Idx = LIS->getInstructionIndex(MI); 927 if (DstInt->liveAt(Idx)) 928 continue; 929 MO.setIsUndef(true); 930 DEBUG(dbgs() << "\tnew undef: " << Idx << '\t' << *MI); 931 } 932 return true; 933} 934 935/// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 936/// update the subregister number if it is not zero. If DstReg is a 937/// physical register and the existing subregister number of the def / use 938/// being updated is not zero, make sure to set it to the correct physical 939/// subregister. 940void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg, 941 unsigned DstReg, 942 unsigned SubIdx) { 943 bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 944 LiveInterval *DstInt = DstIsPhys ? 0 : &LIS->getInterval(DstReg); 945 946 SmallPtrSet<MachineInstr*, 8> Visited; 947 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(SrcReg); 948 MachineInstr *UseMI = I.skipInstruction();) { 949 // Each instruction can only be rewritten once because sub-register 950 // composition is not always idempotent. When SrcReg != DstReg, rewriting 951 // the UseMI operands removes them from the SrcReg use-def chain, but when 952 // SrcReg is DstReg we could encounter UseMI twice if it has multiple 953 // operands mentioning the virtual register. 954 if (SrcReg == DstReg && !Visited.insert(UseMI)) 955 continue; 956 957 SmallVector<unsigned,8> Ops; 958 bool Reads, Writes; 959 tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops); 960 961 // If SrcReg wasn't read, it may still be the case that DstReg is live-in 962 // because SrcReg is a sub-register. 963 if (DstInt && !Reads && SubIdx) 964 Reads = DstInt->liveAt(LIS->getInstructionIndex(UseMI)); 965 966 // Replace SrcReg with DstReg in all UseMI operands. 967 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 968 MachineOperand &MO = UseMI->getOperand(Ops[i]); 969 970 // Adjust <undef> flags in case of sub-register joins. We don't want to 971 // turn a full def into a read-modify-write sub-register def and vice 972 // versa. 973 if (SubIdx && MO.isDef()) 974 MO.setIsUndef(!Reads); 975 976 if (DstIsPhys) 977 MO.substPhysReg(DstReg, *TRI); 978 else 979 MO.substVirtReg(DstReg, SubIdx, *TRI); 980 } 981 982 DEBUG({ 983 dbgs() << "\t\tupdated: "; 984 if (!UseMI->isDebugValue()) 985 dbgs() << LIS->getInstructionIndex(UseMI) << "\t"; 986 dbgs() << *UseMI; 987 }); 988 } 989} 990 991/// canJoinPhys - Return true if a copy involving a physreg should be joined. 992bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) { 993 /// Always join simple intervals that are defined by a single copy from a 994 /// reserved register. This doesn't increase register pressure, so it is 995 /// always beneficial. 996 if (!MRI->isReserved(CP.getDstReg())) { 997 DEBUG(dbgs() << "\tCan only merge into reserved registers.\n"); 998 return false; 999 } 1000 1001 LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg()); 1002 if (CP.isFlipped() && JoinVInt.containsOneValue()) 1003 return true; 1004 1005 DEBUG(dbgs() << "\tCannot join defs into reserved register.\n"); 1006 return false; 1007} 1008 1009/// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 1010/// which are the src/dst of the copy instruction CopyMI. This returns true 1011/// if the copy was successfully coalesced away. If it is not currently 1012/// possible to coalesce this interval, but it may be possible if other 1013/// things get coalesced, then it returns true by reference in 'Again'. 1014bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { 1015 1016 Again = false; 1017 DEBUG(dbgs() << LIS->getInstructionIndex(CopyMI) << '\t' << *CopyMI); 1018 1019 CoalescerPair CP(*TRI); 1020 if (!CP.setRegisters(CopyMI)) { 1021 DEBUG(dbgs() << "\tNot coalescable.\n"); 1022 return false; 1023 } 1024 1025 // Dead code elimination. This really should be handled by MachineDCE, but 1026 // sometimes dead copies slip through, and we can't generate invalid live 1027 // ranges. 1028 if (!CP.isPhys() && CopyMI->allDefsAreDead()) { 1029 DEBUG(dbgs() << "\tCopy is dead.\n"); 1030 DeadDefs.push_back(CopyMI); 1031 eliminateDeadDefs(); 1032 return true; 1033 } 1034 1035 // Eliminate undefs. 1036 if (!CP.isPhys() && eliminateUndefCopy(CopyMI, CP)) { 1037 DEBUG(dbgs() << "\tEliminated copy of <undef> value.\n"); 1038 LIS->RemoveMachineInstrFromMaps(CopyMI); 1039 CopyMI->eraseFromParent(); 1040 return false; // Not coalescable. 1041 } 1042 1043 // Coalesced copies are normally removed immediately, but transformations 1044 // like removeCopyByCommutingDef() can inadvertently create identity copies. 1045 // When that happens, just join the values and remove the copy. 1046 if (CP.getSrcReg() == CP.getDstReg()) { 1047 LiveInterval &LI = LIS->getInterval(CP.getSrcReg()); 1048 DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n'); 1049 LiveRangeQuery LRQ(LI, LIS->getInstructionIndex(CopyMI)); 1050 if (VNInfo *DefVNI = LRQ.valueDefined()) { 1051 VNInfo *ReadVNI = LRQ.valueIn(); 1052 assert(ReadVNI && "No value before copy and no <undef> flag."); 1053 assert(ReadVNI != DefVNI && "Cannot read and define the same value."); 1054 LI.MergeValueNumberInto(DefVNI, ReadVNI); 1055 DEBUG(dbgs() << "\tMerged values: " << LI << '\n'); 1056 } 1057 LIS->RemoveMachineInstrFromMaps(CopyMI); 1058 CopyMI->eraseFromParent(); 1059 return true; 1060 } 1061 1062 // Enforce policies. 1063 if (CP.isPhys()) { 1064 DEBUG(dbgs() << "\tConsidering merging " << PrintReg(CP.getSrcReg(), TRI) 1065 << " with " << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) 1066 << '\n'); 1067 if (!canJoinPhys(CP)) { 1068 // Before giving up coalescing, if definition of source is defined by 1069 // trivial computation, try rematerializing it. 1070 bool IsDefCopy; 1071 if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy)) 1072 return true; 1073 if (IsDefCopy) 1074 Again = true; // May be possible to coalesce later. 1075 return false; 1076 } 1077 } else { 1078 DEBUG({ 1079 dbgs() << "\tConsidering merging to " << CP.getNewRC()->getName() 1080 << " with "; 1081 if (CP.getDstIdx() && CP.getSrcIdx()) 1082 dbgs() << PrintReg(CP.getDstReg()) << " in " 1083 << TRI->getSubRegIndexName(CP.getDstIdx()) << " and " 1084 << PrintReg(CP.getSrcReg()) << " in " 1085 << TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n'; 1086 else 1087 dbgs() << PrintReg(CP.getSrcReg(), TRI) << " in " 1088 << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n'; 1089 }); 1090 1091 // When possible, let DstReg be the larger interval. 1092 if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).ranges.size() > 1093 LIS->getInterval(CP.getDstReg()).ranges.size()) 1094 CP.flip(); 1095 } 1096 1097 // Okay, attempt to join these two intervals. On failure, this returns false. 1098 // Otherwise, if one of the intervals being joined is a physreg, this method 1099 // always canonicalizes DstInt to be it. The output "SrcInt" will not have 1100 // been modified, so we can use this information below to update aliases. 1101 if (!joinIntervals(CP)) { 1102 // Coalescing failed. 1103 1104 // If definition of source is defined by trivial computation, try 1105 // rematerializing it. 1106 bool IsDefCopy; 1107 if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy)) 1108 return true; 1109 1110 // If we can eliminate the copy without merging the live ranges, do so now. 1111 if (!CP.isPartial() && !CP.isPhys()) { 1112 if (adjustCopiesBackFrom(CP, CopyMI) || 1113 removeCopyByCommutingDef(CP, CopyMI)) { 1114 LIS->RemoveMachineInstrFromMaps(CopyMI); 1115 CopyMI->eraseFromParent(); 1116 DEBUG(dbgs() << "\tTrivial!\n"); 1117 return true; 1118 } 1119 } 1120 1121 // Otherwise, we are unable to join the intervals. 1122 DEBUG(dbgs() << "\tInterference!\n"); 1123 Again = true; // May be possible to coalesce later. 1124 return false; 1125 } 1126 1127 // Coalescing to a virtual register that is of a sub-register class of the 1128 // other. Make sure the resulting register is set to the right register class. 1129 if (CP.isCrossClass()) { 1130 ++numCrossRCs; 1131 MRI->setRegClass(CP.getDstReg(), CP.getNewRC()); 1132 } 1133 1134 // Removing sub-register copies can ease the register class constraints. 1135 // Make sure we attempt to inflate the register class of DstReg. 1136 if (!CP.isPhys() && RegClassInfo.isProperSubClass(CP.getNewRC())) 1137 InflateRegs.push_back(CP.getDstReg()); 1138 1139 // CopyMI has been erased by joinIntervals at this point. Remove it from 1140 // ErasedInstrs since copyCoalesceWorkList() won't add a successful join back 1141 // to the work list. This keeps ErasedInstrs from growing needlessly. 1142 ErasedInstrs.erase(CopyMI); 1143 1144 // Rewrite all SrcReg operands to DstReg. 1145 // Also update DstReg operands to include DstIdx if it is set. 1146 if (CP.getDstIdx()) 1147 updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx()); 1148 updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx()); 1149 1150 // SrcReg is guaranteed to be the register whose live interval that is 1151 // being merged. 1152 LIS->removeInterval(CP.getSrcReg()); 1153 1154 // Update regalloc hint. 1155 TRI->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF); 1156 1157 DEBUG({ 1158 dbgs() << "\tJoined. Result = " << PrintReg(CP.getDstReg(), TRI); 1159 if (!CP.isPhys()) 1160 dbgs() << LIS->getInterval(CP.getDstReg()); 1161 dbgs() << '\n'; 1162 }); 1163 1164 ++numJoins; 1165 return true; 1166} 1167 1168/// Attempt joining with a reserved physreg. 1169bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) { 1170 assert(CP.isPhys() && "Must be a physreg copy"); 1171 assert(MRI->isReserved(CP.getDstReg()) && "Not a reserved register"); 1172 LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1173 DEBUG(dbgs() << "\t\tRHS = " << PrintReg(CP.getSrcReg()) << ' ' << RHS 1174 << '\n'); 1175 1176 assert(CP.isFlipped() && RHS.containsOneValue() && 1177 "Invalid join with reserved register"); 1178 1179 // Optimization for reserved registers like ESP. We can only merge with a 1180 // reserved physreg if RHS has a single value that is a copy of CP.DstReg(). 1181 // The live range of the reserved register will look like a set of dead defs 1182 // - we don't properly track the live range of reserved registers. 1183 1184 // Deny any overlapping intervals. This depends on all the reserved 1185 // register live ranges to look like dead defs. 1186 for (MCRegUnitIterator UI(CP.getDstReg(), TRI); UI.isValid(); ++UI) 1187 if (RHS.overlaps(LIS->getRegUnit(*UI))) { 1188 DEBUG(dbgs() << "\t\tInterference: " << PrintRegUnit(*UI, TRI) << '\n'); 1189 return false; 1190 } 1191 1192 // Skip any value computations, we are not adding new values to the 1193 // reserved register. Also skip merging the live ranges, the reserved 1194 // register live range doesn't need to be accurate as long as all the 1195 // defs are there. 1196 1197 // Delete the identity copy. 1198 MachineInstr *CopyMI = MRI->getVRegDef(RHS.reg); 1199 LIS->RemoveMachineInstrFromMaps(CopyMI); 1200 CopyMI->eraseFromParent(); 1201 1202 // We don't track kills for reserved registers. 1203 MRI->clearKillFlags(CP.getSrcReg()); 1204 1205 return true; 1206} 1207 1208//===----------------------------------------------------------------------===// 1209// Interference checking and interval joining 1210//===----------------------------------------------------------------------===// 1211// 1212// In the easiest case, the two live ranges being joined are disjoint, and 1213// there is no interference to consider. It is quite common, though, to have 1214// overlapping live ranges, and we need to check if the interference can be 1215// resolved. 1216// 1217// The live range of a single SSA value forms a sub-tree of the dominator tree. 1218// This means that two SSA values overlap if and only if the def of one value 1219// is contained in the live range of the other value. As a special case, the 1220// overlapping values can be defined at the same index. 1221// 1222// The interference from an overlapping def can be resolved in these cases: 1223// 1224// 1. Coalescable copies. The value is defined by a copy that would become an 1225// identity copy after joining SrcReg and DstReg. The copy instruction will 1226// be removed, and the value will be merged with the source value. 1227// 1228// There can be several copies back and forth, causing many values to be 1229// merged into one. We compute a list of ultimate values in the joined live 1230// range as well as a mappings from the old value numbers. 1231// 1232// 2. IMPLICIT_DEF. This instruction is only inserted to ensure all PHI 1233// predecessors have a live out value. It doesn't cause real interference, 1234// and can be merged into the value it overlaps. Like a coalescable copy, it 1235// can be erased after joining. 1236// 1237// 3. Copy of external value. The overlapping def may be a copy of a value that 1238// is already in the other register. This is like a coalescable copy, but 1239// the live range of the source register must be trimmed after erasing the 1240// copy instruction: 1241// 1242// %src = COPY %ext 1243// %dst = COPY %ext <-- Remove this COPY, trim the live range of %ext. 1244// 1245// 4. Clobbering undefined lanes. Vector registers are sometimes built by 1246// defining one lane at a time: 1247// 1248// %dst:ssub0<def,read-undef> = FOO 1249// %src = BAR 1250// %dst:ssub1<def> = COPY %src 1251// 1252// The live range of %src overlaps the %dst value defined by FOO, but 1253// merging %src into %dst:ssub1 is only going to clobber the ssub1 lane 1254// which was undef anyway. 1255// 1256// The value mapping is more complicated in this case. The final live range 1257// will have different value numbers for both FOO and BAR, but there is no 1258// simple mapping from old to new values. It may even be necessary to add 1259// new PHI values. 1260// 1261// 5. Clobbering dead lanes. A def may clobber a lane of a vector register that 1262// is live, but never read. This can happen because we don't compute 1263// individual live ranges per lane. 1264// 1265// %dst<def> = FOO 1266// %src = BAR 1267// %dst:ssub1<def> = COPY %src 1268// 1269// This kind of interference is only resolved locally. If the clobbered 1270// lane value escapes the block, the join is aborted. 1271 1272namespace { 1273/// Track information about values in a single virtual register about to be 1274/// joined. Objects of this class are always created in pairs - one for each 1275/// side of the CoalescerPair. 1276class JoinVals { 1277 LiveInterval &LI; 1278 1279 // Location of this register in the final joined register. 1280 // Either CP.DstIdx or CP.SrcIdx. 1281 unsigned SubIdx; 1282 1283 // Values that will be present in the final live range. 1284 SmallVectorImpl<VNInfo*> &NewVNInfo; 1285 1286 const CoalescerPair &CP; 1287 LiveIntervals *LIS; 1288 SlotIndexes *Indexes; 1289 const TargetRegisterInfo *TRI; 1290 1291 // Value number assignments. Maps value numbers in LI to entries in NewVNInfo. 1292 // This is suitable for passing to LiveInterval::join(). 1293 SmallVector<int, 8> Assignments; 1294 1295 // Conflict resolution for overlapping values. 1296 enum ConflictResolution { 1297 // No overlap, simply keep this value. 1298 CR_Keep, 1299 1300 // Merge this value into OtherVNI and erase the defining instruction. 1301 // Used for IMPLICIT_DEF, coalescable copies, and copies from external 1302 // values. 1303 CR_Erase, 1304 1305 // Merge this value into OtherVNI but keep the defining instruction. 1306 // This is for the special case where OtherVNI is defined by the same 1307 // instruction. 1308 CR_Merge, 1309 1310 // Keep this value, and have it replace OtherVNI where possible. This 1311 // complicates value mapping since OtherVNI maps to two different values 1312 // before and after this def. 1313 // Used when clobbering undefined or dead lanes. 1314 CR_Replace, 1315 1316 // Unresolved conflict. Visit later when all values have been mapped. 1317 CR_Unresolved, 1318 1319 // Unresolvable conflict. Abort the join. 1320 CR_Impossible 1321 }; 1322 1323 // Per-value info for LI. The lane bit masks are all relative to the final 1324 // joined register, so they can be compared directly between SrcReg and 1325 // DstReg. 1326 struct Val { 1327 ConflictResolution Resolution; 1328 1329 // Lanes written by this def, 0 for unanalyzed values. 1330 unsigned WriteLanes; 1331 1332 // Lanes with defined values in this register. Other lanes are undef and 1333 // safe to clobber. 1334 unsigned ValidLanes; 1335 1336 // Value in LI being redefined by this def. 1337 VNInfo *RedefVNI; 1338 1339 // Value in the other live range that overlaps this def, if any. 1340 VNInfo *OtherVNI; 1341 1342 // Is this value an IMPLICIT_DEF that can be erased? 1343 // 1344 // IMPLICIT_DEF values should only exist at the end of a basic block that 1345 // is a predecessor to a phi-value. These IMPLICIT_DEF instructions can be 1346 // safely erased if they are overlapping a live value in the other live 1347 // interval. 1348 // 1349 // Weird control flow graphs and incomplete PHI handling in 1350 // ProcessImplicitDefs can very rarely create IMPLICIT_DEF values with 1351 // longer live ranges. Such IMPLICIT_DEF values should be treated like 1352 // normal values. 1353 bool ErasableImplicitDef; 1354 1355 // True when the live range of this value will be pruned because of an 1356 // overlapping CR_Replace value in the other live range. 1357 bool Pruned; 1358 1359 // True once Pruned above has been computed. 1360 bool PrunedComputed; 1361 1362 Val() : Resolution(CR_Keep), WriteLanes(0), ValidLanes(0), 1363 RedefVNI(0), OtherVNI(0), ErasableImplicitDef(false), 1364 Pruned(false), PrunedComputed(false) {} 1365 1366 bool isAnalyzed() const { return WriteLanes != 0; } 1367 }; 1368 1369 // One entry per value number in LI. 1370 SmallVector<Val, 8> Vals; 1371 1372 unsigned computeWriteLanes(const MachineInstr *DefMI, bool &Redef); 1373 VNInfo *stripCopies(VNInfo *VNI); 1374 ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other); 1375 void computeAssignment(unsigned ValNo, JoinVals &Other); 1376 bool taintExtent(unsigned, unsigned, JoinVals&, 1377 SmallVectorImpl<std::pair<SlotIndex, unsigned> >&); 1378 bool usesLanes(MachineInstr *MI, unsigned, unsigned, unsigned); 1379 bool isPrunedValue(unsigned ValNo, JoinVals &Other); 1380 1381public: 1382 JoinVals(LiveInterval &li, unsigned subIdx, 1383 SmallVectorImpl<VNInfo*> &newVNInfo, 1384 const CoalescerPair &cp, 1385 LiveIntervals *lis, 1386 const TargetRegisterInfo *tri) 1387 : LI(li), SubIdx(subIdx), NewVNInfo(newVNInfo), CP(cp), LIS(lis), 1388 Indexes(LIS->getSlotIndexes()), TRI(tri), 1389 Assignments(LI.getNumValNums(), -1), Vals(LI.getNumValNums()) 1390 {} 1391 1392 /// Analyze defs in LI and compute a value mapping in NewVNInfo. 1393 /// Returns false if any conflicts were impossible to resolve. 1394 bool mapValues(JoinVals &Other); 1395 1396 /// Try to resolve conflicts that require all values to be mapped. 1397 /// Returns false if any conflicts were impossible to resolve. 1398 bool resolveConflicts(JoinVals &Other); 1399 1400 /// Prune the live range of values in Other.LI where they would conflict with 1401 /// CR_Replace values in LI. Collect end points for restoring the live range 1402 /// after joining. 1403 void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints); 1404 1405 /// Erase any machine instructions that have been coalesced away. 1406 /// Add erased instructions to ErasedInstrs. 1407 /// Add foreign virtual registers to ShrinkRegs if their live range ended at 1408 /// the erased instrs. 1409 void eraseInstrs(SmallPtrSet<MachineInstr*, 8> &ErasedInstrs, 1410 SmallVectorImpl<unsigned> &ShrinkRegs); 1411 1412 /// Get the value assignments suitable for passing to LiveInterval::join. 1413 const int *getAssignments() const { return Assignments.data(); } 1414}; 1415} // end anonymous namespace 1416 1417/// Compute the bitmask of lanes actually written by DefMI. 1418/// Set Redef if there are any partial register definitions that depend on the 1419/// previous value of the register. 1420unsigned JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef) { 1421 unsigned L = 0; 1422 for (ConstMIOperands MO(DefMI); MO.isValid(); ++MO) { 1423 if (!MO->isReg() || MO->getReg() != LI.reg || !MO->isDef()) 1424 continue; 1425 L |= TRI->getSubRegIndexLaneMask( 1426 TRI->composeSubRegIndices(SubIdx, MO->getSubReg())); 1427 if (MO->readsReg()) 1428 Redef = true; 1429 } 1430 return L; 1431} 1432 1433/// Find the ultimate value that VNI was copied from. 1434VNInfo *JoinVals::stripCopies(VNInfo *VNI) { 1435 while (!VNI->isPHIDef()) { 1436 MachineInstr *MI = Indexes->getInstructionFromIndex(VNI->def); 1437 assert(MI && "No defining instruction"); 1438 if (!MI->isFullCopy()) 1439 break; 1440 unsigned Reg = MI->getOperand(1).getReg(); 1441 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1442 break; 1443 LiveRangeQuery LRQ(LIS->getInterval(Reg), VNI->def); 1444 if (!LRQ.valueIn()) 1445 break; 1446 VNI = LRQ.valueIn(); 1447 } 1448 return VNI; 1449} 1450 1451/// Analyze ValNo in this live range, and set all fields of Vals[ValNo]. 1452/// Return a conflict resolution when possible, but leave the hard cases as 1453/// CR_Unresolved. 1454/// Recursively calls computeAssignment() on this and Other, guaranteeing that 1455/// both OtherVNI and RedefVNI have been analyzed and mapped before returning. 1456/// The recursion always goes upwards in the dominator tree, making loops 1457/// impossible. 1458JoinVals::ConflictResolution 1459JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) { 1460 Val &V = Vals[ValNo]; 1461 assert(!V.isAnalyzed() && "Value has already been analyzed!"); 1462 VNInfo *VNI = LI.getValNumInfo(ValNo); 1463 if (VNI->isUnused()) { 1464 V.WriteLanes = ~0u; 1465 return CR_Keep; 1466 } 1467 1468 // Get the instruction defining this value, compute the lanes written. 1469 const MachineInstr *DefMI = 0; 1470 if (VNI->isPHIDef()) { 1471 // Conservatively assume that all lanes in a PHI are valid. 1472 V.ValidLanes = V.WriteLanes = TRI->getSubRegIndexLaneMask(SubIdx); 1473 } else { 1474 DefMI = Indexes->getInstructionFromIndex(VNI->def); 1475 bool Redef = false; 1476 V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef); 1477 1478 // If this is a read-modify-write instruction, there may be more valid 1479 // lanes than the ones written by this instruction. 1480 // This only covers partial redef operands. DefMI may have normal use 1481 // operands reading the register. They don't contribute valid lanes. 1482 // 1483 // This adds ssub1 to the set of valid lanes in %src: 1484 // 1485 // %src:ssub1<def> = FOO 1486 // 1487 // This leaves only ssub1 valid, making any other lanes undef: 1488 // 1489 // %src:ssub1<def,read-undef> = FOO %src:ssub2 1490 // 1491 // The <read-undef> flag on the def operand means that old lane values are 1492 // not important. 1493 if (Redef) { 1494 V.RedefVNI = LiveRangeQuery(LI, VNI->def).valueIn(); 1495 assert(V.RedefVNI && "Instruction is reading nonexistent value"); 1496 computeAssignment(V.RedefVNI->id, Other); 1497 V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes; 1498 } 1499 1500 // An IMPLICIT_DEF writes undef values. 1501 if (DefMI->isImplicitDef()) { 1502 // We normally expect IMPLICIT_DEF values to be live only until the end 1503 // of their block. If the value is really live longer and gets pruned in 1504 // another block, this flag is cleared again. 1505 V.ErasableImplicitDef = true; 1506 V.ValidLanes &= ~V.WriteLanes; 1507 } 1508 } 1509 1510 // Find the value in Other that overlaps VNI->def, if any. 1511 LiveRangeQuery OtherLRQ(Other.LI, VNI->def); 1512 1513 // It is possible that both values are defined by the same instruction, or 1514 // the values are PHIs defined in the same block. When that happens, the two 1515 // values should be merged into one, but not into any preceding value. 1516 // The first value defined or visited gets CR_Keep, the other gets CR_Merge. 1517 if (VNInfo *OtherVNI = OtherLRQ.valueDefined()) { 1518 assert(SlotIndex::isSameInstr(VNI->def, OtherVNI->def) && "Broken LRQ"); 1519 1520 // One value stays, the other is merged. Keep the earlier one, or the first 1521 // one we see. 1522 if (OtherVNI->def < VNI->def) 1523 Other.computeAssignment(OtherVNI->id, *this); 1524 else if (VNI->def < OtherVNI->def && OtherLRQ.valueIn()) { 1525 // This is an early-clobber def overlapping a live-in value in the other 1526 // register. Not mergeable. 1527 V.OtherVNI = OtherLRQ.valueIn(); 1528 return CR_Impossible; 1529 } 1530 V.OtherVNI = OtherVNI; 1531 Val &OtherV = Other.Vals[OtherVNI->id]; 1532 // Keep this value, check for conflicts when analyzing OtherVNI. 1533 if (!OtherV.isAnalyzed()) 1534 return CR_Keep; 1535 // Both sides have been analyzed now. 1536 // Allow overlapping PHI values. Any real interference would show up in a 1537 // predecessor, the PHI itself can't introduce any conflicts. 1538 if (VNI->isPHIDef()) 1539 return CR_Merge; 1540 if (V.ValidLanes & OtherV.ValidLanes) 1541 // Overlapping lanes can't be resolved. 1542 return CR_Impossible; 1543 else 1544 return CR_Merge; 1545 } 1546 1547 // No simultaneous def. Is Other live at the def? 1548 V.OtherVNI = OtherLRQ.valueIn(); 1549 if (!V.OtherVNI) 1550 // No overlap, no conflict. 1551 return CR_Keep; 1552 1553 assert(!SlotIndex::isSameInstr(VNI->def, V.OtherVNI->def) && "Broken LRQ"); 1554 1555 // We have overlapping values, or possibly a kill of Other. 1556 // Recursively compute assignments up the dominator tree. 1557 Other.computeAssignment(V.OtherVNI->id, *this); 1558 Val &OtherV = Other.Vals[V.OtherVNI->id]; 1559 1560 // Check if OtherV is an IMPLICIT_DEF that extends beyond its basic block. 1561 // This shouldn't normally happen, but ProcessImplicitDefs can leave such 1562 // IMPLICIT_DEF instructions behind, and there is nothing wrong with it 1563 // technically. 1564 // 1565 // WHen it happens, treat that IMPLICIT_DEF as a normal value, and don't try 1566 // to erase the IMPLICIT_DEF instruction. 1567 if (OtherV.ErasableImplicitDef && DefMI && 1568 DefMI->getParent() != Indexes->getMBBFromIndex(V.OtherVNI->def)) { 1569 DEBUG(dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def 1570 << " extends into BB#" << DefMI->getParent()->getNumber() 1571 << ", keeping it.\n"); 1572 OtherV.ErasableImplicitDef = false; 1573 } 1574 1575 // Allow overlapping PHI values. Any real interference would show up in a 1576 // predecessor, the PHI itself can't introduce any conflicts. 1577 if (VNI->isPHIDef()) 1578 return CR_Replace; 1579 1580 // Check for simple erasable conflicts. 1581 if (DefMI->isImplicitDef()) 1582 return CR_Erase; 1583 1584 // Include the non-conflict where DefMI is a coalescable copy that kills 1585 // OtherVNI. We still want the copy erased and value numbers merged. 1586 if (CP.isCoalescable(DefMI)) { 1587 // Some of the lanes copied from OtherVNI may be undef, making them undef 1588 // here too. 1589 V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes; 1590 return CR_Erase; 1591 } 1592 1593 // This may not be a real conflict if DefMI simply kills Other and defines 1594 // VNI. 1595 if (OtherLRQ.isKill() && OtherLRQ.endPoint() <= VNI->def) 1596 return CR_Keep; 1597 1598 // Handle the case where VNI and OtherVNI can be proven to be identical: 1599 // 1600 // %other = COPY %ext 1601 // %this = COPY %ext <-- Erase this copy 1602 // 1603 if (DefMI->isFullCopy() && !CP.isPartial() && 1604 stripCopies(VNI) == stripCopies(V.OtherVNI)) 1605 return CR_Erase; 1606 1607 // If the lanes written by this instruction were all undef in OtherVNI, it is 1608 // still safe to join the live ranges. This can't be done with a simple value 1609 // mapping, though - OtherVNI will map to multiple values: 1610 // 1611 // 1 %dst:ssub0 = FOO <-- OtherVNI 1612 // 2 %src = BAR <-- VNI 1613 // 3 %dst:ssub1 = COPY %src<kill> <-- Eliminate this copy. 1614 // 4 BAZ %dst<kill> 1615 // 5 QUUX %src<kill> 1616 // 1617 // Here OtherVNI will map to itself in [1;2), but to VNI in [2;5). CR_Replace 1618 // handles this complex value mapping. 1619 if ((V.WriteLanes & OtherV.ValidLanes) == 0) 1620 return CR_Replace; 1621 1622 // If the other live range is killed by DefMI and the live ranges are still 1623 // overlapping, it must be because we're looking at an early clobber def: 1624 // 1625 // %dst<def,early-clobber> = ASM %src<kill> 1626 // 1627 // In this case, it is illegal to merge the two live ranges since the early 1628 // clobber def would clobber %src before it was read. 1629 if (OtherLRQ.isKill()) { 1630 // This case where the def doesn't overlap the kill is handled above. 1631 assert(VNI->def.isEarlyClobber() && 1632 "Only early clobber defs can overlap a kill"); 1633 return CR_Impossible; 1634 } 1635 1636 // VNI is clobbering live lanes in OtherVNI, but there is still the 1637 // possibility that no instructions actually read the clobbered lanes. 1638 // If we're clobbering all the lanes in OtherVNI, at least one must be read. 1639 // Otherwise Other.LI wouldn't be live here. 1640 if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes) == 0) 1641 return CR_Impossible; 1642 1643 // We need to verify that no instructions are reading the clobbered lanes. To 1644 // save compile time, we'll only check that locally. Don't allow the tainted 1645 // value to escape the basic block. 1646 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1647 if (OtherLRQ.endPoint() >= Indexes->getMBBEndIdx(MBB)) 1648 return CR_Impossible; 1649 1650 // There are still some things that could go wrong besides clobbered lanes 1651 // being read, for example OtherVNI may be only partially redefined in MBB, 1652 // and some clobbered lanes could escape the block. Save this analysis for 1653 // resolveConflicts() when all values have been mapped. We need to know 1654 // RedefVNI and WriteLanes for any later defs in MBB, and we can't compute 1655 // that now - the recursive analyzeValue() calls must go upwards in the 1656 // dominator tree. 1657 return CR_Unresolved; 1658} 1659 1660/// Compute the value assignment for ValNo in LI. 1661/// This may be called recursively by analyzeValue(), but never for a ValNo on 1662/// the stack. 1663void JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) { 1664 Val &V = Vals[ValNo]; 1665 if (V.isAnalyzed()) { 1666 // Recursion should always move up the dominator tree, so ValNo is not 1667 // supposed to reappear before it has been assigned. 1668 assert(Assignments[ValNo] != -1 && "Bad recursion?"); 1669 return; 1670 } 1671 switch ((V.Resolution = analyzeValue(ValNo, Other))) { 1672 case CR_Erase: 1673 case CR_Merge: 1674 // Merge this ValNo into OtherVNI. 1675 assert(V.OtherVNI && "OtherVNI not assigned, can't merge."); 1676 assert(Other.Vals[V.OtherVNI->id].isAnalyzed() && "Missing recursion"); 1677 Assignments[ValNo] = Other.Assignments[V.OtherVNI->id]; 1678 DEBUG(dbgs() << "\t\tmerge " << PrintReg(LI.reg) << ':' << ValNo << '@' 1679 << LI.getValNumInfo(ValNo)->def << " into " 1680 << PrintReg(Other.LI.reg) << ':' << V.OtherVNI->id << '@' 1681 << V.OtherVNI->def << " --> @" 1682 << NewVNInfo[Assignments[ValNo]]->def << '\n'); 1683 break; 1684 case CR_Replace: 1685 case CR_Unresolved: 1686 // The other value is going to be pruned if this join is successful. 1687 assert(V.OtherVNI && "OtherVNI not assigned, can't prune"); 1688 Other.Vals[V.OtherVNI->id].Pruned = true; 1689 // Fall through. 1690 default: 1691 // This value number needs to go in the final joined live range. 1692 Assignments[ValNo] = NewVNInfo.size(); 1693 NewVNInfo.push_back(LI.getValNumInfo(ValNo)); 1694 break; 1695 } 1696} 1697 1698bool JoinVals::mapValues(JoinVals &Other) { 1699 for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1700 computeAssignment(i, Other); 1701 if (Vals[i].Resolution == CR_Impossible) { 1702 DEBUG(dbgs() << "\t\tinterference at " << PrintReg(LI.reg) << ':' << i 1703 << '@' << LI.getValNumInfo(i)->def << '\n'); 1704 return false; 1705 } 1706 } 1707 return true; 1708} 1709 1710/// Assuming ValNo is going to clobber some valid lanes in Other.LI, compute 1711/// the extent of the tainted lanes in the block. 1712/// 1713/// Multiple values in Other.LI can be affected since partial redefinitions can 1714/// preserve previously tainted lanes. 1715/// 1716/// 1 %dst = VLOAD <-- Define all lanes in %dst 1717/// 2 %src = FOO <-- ValNo to be joined with %dst:ssub0 1718/// 3 %dst:ssub1 = BAR <-- Partial redef doesn't clear taint in ssub0 1719/// 4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read 1720/// 1721/// For each ValNo in Other that is affected, add an (EndIndex, TaintedLanes) 1722/// entry to TaintedVals. 1723/// 1724/// Returns false if the tainted lanes extend beyond the basic block. 1725bool JoinVals:: 1726taintExtent(unsigned ValNo, unsigned TaintedLanes, JoinVals &Other, 1727 SmallVectorImpl<std::pair<SlotIndex, unsigned> > &TaintExtent) { 1728 VNInfo *VNI = LI.getValNumInfo(ValNo); 1729 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1730 SlotIndex MBBEnd = Indexes->getMBBEndIdx(MBB); 1731 1732 // Scan Other.LI from VNI.def to MBBEnd. 1733 LiveInterval::iterator OtherI = Other.LI.find(VNI->def); 1734 assert(OtherI != Other.LI.end() && "No conflict?"); 1735 do { 1736 // OtherI is pointing to a tainted value. Abort the join if the tainted 1737 // lanes escape the block. 1738 SlotIndex End = OtherI->end; 1739 if (End >= MBBEnd) { 1740 DEBUG(dbgs() << "\t\ttaints global " << PrintReg(Other.LI.reg) << ':' 1741 << OtherI->valno->id << '@' << OtherI->start << '\n'); 1742 return false; 1743 } 1744 DEBUG(dbgs() << "\t\ttaints local " << PrintReg(Other.LI.reg) << ':' 1745 << OtherI->valno->id << '@' << OtherI->start 1746 << " to " << End << '\n'); 1747 // A dead def is not a problem. 1748 if (End.isDead()) 1749 break; 1750 TaintExtent.push_back(std::make_pair(End, TaintedLanes)); 1751 1752 // Check for another def in the MBB. 1753 if (++OtherI == Other.LI.end() || OtherI->start >= MBBEnd) 1754 break; 1755 1756 // Lanes written by the new def are no longer tainted. 1757 const Val &OV = Other.Vals[OtherI->valno->id]; 1758 TaintedLanes &= ~OV.WriteLanes; 1759 if (!OV.RedefVNI) 1760 break; 1761 } while (TaintedLanes); 1762 return true; 1763} 1764 1765/// Return true if MI uses any of the given Lanes from Reg. 1766/// This does not include partial redefinitions of Reg. 1767bool JoinVals::usesLanes(MachineInstr *MI, unsigned Reg, unsigned SubIdx, 1768 unsigned Lanes) { 1769 if (MI->isDebugValue()) 1770 return false; 1771 for (ConstMIOperands MO(MI); MO.isValid(); ++MO) { 1772 if (!MO->isReg() || MO->isDef() || MO->getReg() != Reg) 1773 continue; 1774 if (!MO->readsReg()) 1775 continue; 1776 if (Lanes & TRI->getSubRegIndexLaneMask( 1777 TRI->composeSubRegIndices(SubIdx, MO->getSubReg()))) 1778 return true; 1779 } 1780 return false; 1781} 1782 1783bool JoinVals::resolveConflicts(JoinVals &Other) { 1784 for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1785 Val &V = Vals[i]; 1786 assert (V.Resolution != CR_Impossible && "Unresolvable conflict"); 1787 if (V.Resolution != CR_Unresolved) 1788 continue; 1789 DEBUG(dbgs() << "\t\tconflict at " << PrintReg(LI.reg) << ':' << i 1790 << '@' << LI.getValNumInfo(i)->def << '\n'); 1791 ++NumLaneConflicts; 1792 assert(V.OtherVNI && "Inconsistent conflict resolution."); 1793 VNInfo *VNI = LI.getValNumInfo(i); 1794 const Val &OtherV = Other.Vals[V.OtherVNI->id]; 1795 1796 // VNI is known to clobber some lanes in OtherVNI. If we go ahead with the 1797 // join, those lanes will be tainted with a wrong value. Get the extent of 1798 // the tainted lanes. 1799 unsigned TaintedLanes = V.WriteLanes & OtherV.ValidLanes; 1800 SmallVector<std::pair<SlotIndex, unsigned>, 8> TaintExtent; 1801 if (!taintExtent(i, TaintedLanes, Other, TaintExtent)) 1802 // Tainted lanes would extend beyond the basic block. 1803 return false; 1804 1805 assert(!TaintExtent.empty() && "There should be at least one conflict."); 1806 1807 // Now look at the instructions from VNI->def to TaintExtent (inclusive). 1808 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1809 MachineBasicBlock::iterator MI = MBB->begin(); 1810 if (!VNI->isPHIDef()) { 1811 MI = Indexes->getInstructionFromIndex(VNI->def); 1812 // No need to check the instruction defining VNI for reads. 1813 ++MI; 1814 } 1815 assert(!SlotIndex::isSameInstr(VNI->def, TaintExtent.front().first) && 1816 "Interference ends on VNI->def. Should have been handled earlier"); 1817 MachineInstr *LastMI = 1818 Indexes->getInstructionFromIndex(TaintExtent.front().first); 1819 assert(LastMI && "Range must end at a proper instruction"); 1820 unsigned TaintNum = 0; 1821 for(;;) { 1822 assert(MI != MBB->end() && "Bad LastMI"); 1823 if (usesLanes(MI, Other.LI.reg, Other.SubIdx, TaintedLanes)) { 1824 DEBUG(dbgs() << "\t\ttainted lanes used by: " << *MI); 1825 return false; 1826 } 1827 // LastMI is the last instruction to use the current value. 1828 if (&*MI == LastMI) { 1829 if (++TaintNum == TaintExtent.size()) 1830 break; 1831 LastMI = Indexes->getInstructionFromIndex(TaintExtent[TaintNum].first); 1832 assert(LastMI && "Range must end at a proper instruction"); 1833 TaintedLanes = TaintExtent[TaintNum].second; 1834 } 1835 ++MI; 1836 } 1837 1838 // The tainted lanes are unused. 1839 V.Resolution = CR_Replace; 1840 ++NumLaneResolves; 1841 } 1842 return true; 1843} 1844 1845// Determine if ValNo is a copy of a value number in LI or Other.LI that will 1846// be pruned: 1847// 1848// %dst = COPY %src 1849// %src = COPY %dst <-- This value to be pruned. 1850// %dst = COPY %src <-- This value is a copy of a pruned value. 1851// 1852bool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) { 1853 Val &V = Vals[ValNo]; 1854 if (V.Pruned || V.PrunedComputed) 1855 return V.Pruned; 1856 1857 if (V.Resolution != CR_Erase && V.Resolution != CR_Merge) 1858 return V.Pruned; 1859 1860 // Follow copies up the dominator tree and check if any intermediate value 1861 // has been pruned. 1862 V.PrunedComputed = true; 1863 V.Pruned = Other.isPrunedValue(V.OtherVNI->id, *this); 1864 return V.Pruned; 1865} 1866 1867void JoinVals::pruneValues(JoinVals &Other, 1868 SmallVectorImpl<SlotIndex> &EndPoints) { 1869 for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1870 SlotIndex Def = LI.getValNumInfo(i)->def; 1871 switch (Vals[i].Resolution) { 1872 case CR_Keep: 1873 break; 1874 case CR_Replace: { 1875 // This value takes precedence over the value in Other.LI. 1876 LIS->pruneValue(&Other.LI, Def, &EndPoints); 1877 // Check if we're replacing an IMPLICIT_DEF value. The IMPLICIT_DEF 1878 // instructions are only inserted to provide a live-out value for PHI 1879 // predecessors, so the instruction should simply go away once its value 1880 // has been replaced. 1881 Val &OtherV = Other.Vals[Vals[i].OtherVNI->id]; 1882 bool EraseImpDef = OtherV.ErasableImplicitDef && 1883 OtherV.Resolution == CR_Keep; 1884 if (!Def.isBlock()) { 1885 // Remove <def,read-undef> flags. This def is now a partial redef. 1886 // Also remove <def,dead> flags since the joined live range will 1887 // continue past this instruction. 1888 for (MIOperands MO(Indexes->getInstructionFromIndex(Def)); 1889 MO.isValid(); ++MO) 1890 if (MO->isReg() && MO->isDef() && MO->getReg() == LI.reg) { 1891 MO->setIsUndef(EraseImpDef); 1892 MO->setIsDead(false); 1893 } 1894 // This value will reach instructions below, but we need to make sure 1895 // the live range also reaches the instruction at Def. 1896 if (!EraseImpDef) 1897 EndPoints.push_back(Def); 1898 } 1899 DEBUG(dbgs() << "\t\tpruned " << PrintReg(Other.LI.reg) << " at " << Def 1900 << ": " << Other.LI << '\n'); 1901 break; 1902 } 1903 case CR_Erase: 1904 case CR_Merge: 1905 if (isPrunedValue(i, Other)) { 1906 // This value is ultimately a copy of a pruned value in LI or Other.LI. 1907 // We can no longer trust the value mapping computed by 1908 // computeAssignment(), the value that was originally copied could have 1909 // been replaced. 1910 LIS->pruneValue(&LI, Def, &EndPoints); 1911 DEBUG(dbgs() << "\t\tpruned all of " << PrintReg(LI.reg) << " at " 1912 << Def << ": " << LI << '\n'); 1913 } 1914 break; 1915 case CR_Unresolved: 1916 case CR_Impossible: 1917 llvm_unreachable("Unresolved conflicts"); 1918 } 1919 } 1920} 1921 1922void JoinVals::eraseInstrs(SmallPtrSet<MachineInstr*, 8> &ErasedInstrs, 1923 SmallVectorImpl<unsigned> &ShrinkRegs) { 1924 for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1925 // Get the def location before markUnused() below invalidates it. 1926 SlotIndex Def = LI.getValNumInfo(i)->def; 1927 switch (Vals[i].Resolution) { 1928 case CR_Keep: 1929 // If an IMPLICIT_DEF value is pruned, it doesn't serve a purpose any 1930 // longer. The IMPLICIT_DEF instructions are only inserted by 1931 // PHIElimination to guarantee that all PHI predecessors have a value. 1932 if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned) 1933 break; 1934 // Remove value number i from LI. Note that this VNInfo is still present 1935 // in NewVNInfo, so it will appear as an unused value number in the final 1936 // joined interval. 1937 LI.getValNumInfo(i)->markUnused(); 1938 LI.removeValNo(LI.getValNumInfo(i)); 1939 DEBUG(dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LI << '\n'); 1940 // FALL THROUGH. 1941 1942 case CR_Erase: { 1943 MachineInstr *MI = Indexes->getInstructionFromIndex(Def); 1944 assert(MI && "No instruction to erase"); 1945 if (MI->isCopy()) { 1946 unsigned Reg = MI->getOperand(1).getReg(); 1947 if (TargetRegisterInfo::isVirtualRegister(Reg) && 1948 Reg != CP.getSrcReg() && Reg != CP.getDstReg()) 1949 ShrinkRegs.push_back(Reg); 1950 } 1951 ErasedInstrs.insert(MI); 1952 DEBUG(dbgs() << "\t\terased:\t" << Def << '\t' << *MI); 1953 LIS->RemoveMachineInstrFromMaps(MI); 1954 MI->eraseFromParent(); 1955 break; 1956 } 1957 default: 1958 break; 1959 } 1960 } 1961} 1962 1963bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) { 1964 SmallVector<VNInfo*, 16> NewVNInfo; 1965 LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1966 LiveInterval &LHS = LIS->getInterval(CP.getDstReg()); 1967 JoinVals RHSVals(RHS, CP.getSrcIdx(), NewVNInfo, CP, LIS, TRI); 1968 JoinVals LHSVals(LHS, CP.getDstIdx(), NewVNInfo, CP, LIS, TRI); 1969 1970 DEBUG(dbgs() << "\t\tRHS = " << PrintReg(CP.getSrcReg()) << ' ' << RHS 1971 << "\n\t\tLHS = " << PrintReg(CP.getDstReg()) << ' ' << LHS 1972 << '\n'); 1973 1974 // First compute NewVNInfo and the simple value mappings. 1975 // Detect impossible conflicts early. 1976 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) 1977 return false; 1978 1979 // Some conflicts can only be resolved after all values have been mapped. 1980 if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals)) 1981 return false; 1982 1983 // All clear, the live ranges can be merged. 1984 1985 // The merging algorithm in LiveInterval::join() can't handle conflicting 1986 // value mappings, so we need to remove any live ranges that overlap a 1987 // CR_Replace resolution. Collect a set of end points that can be used to 1988 // restore the live range after joining. 1989 SmallVector<SlotIndex, 8> EndPoints; 1990 LHSVals.pruneValues(RHSVals, EndPoints); 1991 RHSVals.pruneValues(LHSVals, EndPoints); 1992 1993 // Erase COPY and IMPLICIT_DEF instructions. This may cause some external 1994 // registers to require trimming. 1995 SmallVector<unsigned, 8> ShrinkRegs; 1996 LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs); 1997 RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs); 1998 while (!ShrinkRegs.empty()) 1999 LIS->shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val())); 2000 2001 // Join RHS into LHS. 2002 LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo, 2003 MRI); 2004 2005 // Kill flags are going to be wrong if the live ranges were overlapping. 2006 // Eventually, we should simply clear all kill flags when computing live 2007 // ranges. They are reinserted after register allocation. 2008 MRI->clearKillFlags(LHS.reg); 2009 MRI->clearKillFlags(RHS.reg); 2010 2011 if (EndPoints.empty()) 2012 return true; 2013 2014 // Recompute the parts of the live range we had to remove because of 2015 // CR_Replace conflicts. 2016 DEBUG(dbgs() << "\t\trestoring liveness to " << EndPoints.size() 2017 << " points: " << LHS << '\n'); 2018 LIS->extendToIndices(&LHS, EndPoints); 2019 return true; 2020} 2021 2022/// joinIntervals - Attempt to join these two intervals. On failure, this 2023/// returns false. 2024bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) { 2025 return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP); 2026} 2027 2028namespace { 2029// Information concerning MBB coalescing priority. 2030struct MBBPriorityInfo { 2031 MachineBasicBlock *MBB; 2032 unsigned Depth; 2033 bool IsSplit; 2034 2035 MBBPriorityInfo(MachineBasicBlock *mbb, unsigned depth, bool issplit) 2036 : MBB(mbb), Depth(depth), IsSplit(issplit) {} 2037}; 2038} 2039 2040// C-style comparator that sorts first based on the loop depth of the basic 2041// block (the unsigned), and then on the MBB number. 2042// 2043// EnableGlobalCopies assumes that the primary sort key is loop depth. 2044static int compareMBBPriority(const void *L, const void *R) { 2045 const MBBPriorityInfo *LHS = static_cast<const MBBPriorityInfo*>(L); 2046 const MBBPriorityInfo *RHS = static_cast<const MBBPriorityInfo*>(R); 2047 // Deeper loops first 2048 if (LHS->Depth != RHS->Depth) 2049 return LHS->Depth > RHS->Depth ? -1 : 1; 2050 2051 // Try to unsplit critical edges next. 2052 if (LHS->IsSplit != RHS->IsSplit) 2053 return LHS->IsSplit ? -1 : 1; 2054 2055 // Prefer blocks that are more connected in the CFG. This takes care of 2056 // the most difficult copies first while intervals are short. 2057 unsigned cl = LHS->MBB->pred_size() + LHS->MBB->succ_size(); 2058 unsigned cr = RHS->MBB->pred_size() + RHS->MBB->succ_size(); 2059 if (cl != cr) 2060 return cl > cr ? -1 : 1; 2061 2062 // As a last resort, sort by block number. 2063 return LHS->MBB->getNumber() < RHS->MBB->getNumber() ? -1 : 1; 2064} 2065 2066/// \returns true if the given copy uses or defines a local live range. 2067static bool isLocalCopy(MachineInstr *Copy, const LiveIntervals *LIS) { 2068 if (!Copy->isCopy()) 2069 return false; 2070 2071 if (Copy->getOperand(1).isUndef()) 2072 return false; 2073 2074 unsigned SrcReg = Copy->getOperand(1).getReg(); 2075 unsigned DstReg = Copy->getOperand(0).getReg(); 2076 if (TargetRegisterInfo::isPhysicalRegister(SrcReg) 2077 || TargetRegisterInfo::isPhysicalRegister(DstReg)) 2078 return false; 2079 2080 return LIS->intervalIsInOneMBB(LIS->getInterval(SrcReg)) 2081 || LIS->intervalIsInOneMBB(LIS->getInterval(DstReg)); 2082} 2083 2084// Try joining WorkList copies starting from index From. 2085// Null out any successful joins. 2086bool RegisterCoalescer:: 2087copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList) { 2088 bool Progress = false; 2089 for (unsigned i = 0, e = CurrList.size(); i != e; ++i) { 2090 if (!CurrList[i]) 2091 continue; 2092 // Skip instruction pointers that have already been erased, for example by 2093 // dead code elimination. 2094 if (ErasedInstrs.erase(CurrList[i])) { 2095 CurrList[i] = 0; 2096 continue; 2097 } 2098 bool Again = false; 2099 bool Success = joinCopy(CurrList[i], Again); 2100 Progress |= Success; 2101 if (Success || !Again) 2102 CurrList[i] = 0; 2103 } 2104 return Progress; 2105} 2106 2107void 2108RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) { 2109 DEBUG(dbgs() << MBB->getName() << ":\n"); 2110 2111 // Collect all copy-like instructions in MBB. Don't start coalescing anything 2112 // yet, it might invalidate the iterator. 2113 const unsigned PrevSize = WorkList.size(); 2114 if (JoinGlobalCopies) { 2115 // Coalesce copies bottom-up to coalesce local defs before local uses. They 2116 // are not inherently easier to resolve, but slightly preferable until we 2117 // have local live range splitting. In particular this is required by 2118 // cmp+jmp macro fusion. 2119 for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 2120 MII != E; ++MII) { 2121 if (!MII->isCopyLike()) 2122 continue; 2123 if (isLocalCopy(&(*MII), LIS)) 2124 LocalWorkList.push_back(&(*MII)); 2125 else 2126 WorkList.push_back(&(*MII)); 2127 } 2128 } 2129 else { 2130 for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 2131 MII != E; ++MII) 2132 if (MII->isCopyLike()) 2133 WorkList.push_back(MII); 2134 } 2135 // Try coalescing the collected copies immediately, and remove the nulls. 2136 // This prevents the WorkList from getting too large since most copies are 2137 // joinable on the first attempt. 2138 MutableArrayRef<MachineInstr*> 2139 CurrList(WorkList.begin() + PrevSize, WorkList.end()); 2140 if (copyCoalesceWorkList(CurrList)) 2141 WorkList.erase(std::remove(WorkList.begin() + PrevSize, WorkList.end(), 2142 (MachineInstr*)0), WorkList.end()); 2143} 2144 2145void RegisterCoalescer::coalesceLocals() { 2146 copyCoalesceWorkList(LocalWorkList); 2147 for (unsigned j = 0, je = LocalWorkList.size(); j != je; ++j) { 2148 if (LocalWorkList[j]) 2149 WorkList.push_back(LocalWorkList[j]); 2150 } 2151 LocalWorkList.clear(); 2152} 2153 2154void RegisterCoalescer::joinAllIntervals() { 2155 DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n"); 2156 assert(WorkList.empty() && LocalWorkList.empty() && "Old data still around."); 2157 2158 std::vector<MBBPriorityInfo> MBBs; 2159 MBBs.reserve(MF->size()); 2160 for (MachineFunction::iterator I = MF->begin(), E = MF->end();I != E;++I){ 2161 MachineBasicBlock *MBB = I; 2162 MBBs.push_back(MBBPriorityInfo(MBB, Loops->getLoopDepth(MBB), 2163 JoinSplitEdges && isSplitEdge(MBB))); 2164 } 2165 array_pod_sort(MBBs.begin(), MBBs.end(), compareMBBPriority); 2166 2167 // Coalesce intervals in MBB priority order. 2168 unsigned CurrDepth = UINT_MAX; 2169 for (unsigned i = 0, e = MBBs.size(); i != e; ++i) { 2170 // Try coalescing the collected local copies for deeper loops. 2171 if (JoinGlobalCopies && MBBs[i].Depth < CurrDepth) { 2172 coalesceLocals(); 2173 CurrDepth = MBBs[i].Depth; 2174 } 2175 copyCoalesceInMBB(MBBs[i].MBB); 2176 } 2177 coalesceLocals(); 2178 2179 // Joining intervals can allow other intervals to be joined. Iteratively join 2180 // until we make no progress. 2181 while (copyCoalesceWorkList(WorkList)) 2182 /* empty */ ; 2183} 2184 2185void RegisterCoalescer::releaseMemory() { 2186 ErasedInstrs.clear(); 2187 WorkList.clear(); 2188 DeadDefs.clear(); 2189 InflateRegs.clear(); 2190} 2191 2192bool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) { 2193 MF = &fn; 2194 MRI = &fn.getRegInfo(); 2195 TM = &fn.getTarget(); 2196 TRI = TM->getRegisterInfo(); 2197 TII = TM->getInstrInfo(); 2198 LIS = &getAnalysis<LiveIntervals>(); 2199 AA = &getAnalysis<AliasAnalysis>(); 2200 Loops = &getAnalysis<MachineLoopInfo>(); 2201 2202 const TargetSubtargetInfo &ST = TM->getSubtarget<TargetSubtargetInfo>(); 2203 if (EnableGlobalCopies == cl::BOU_UNSET) 2204 JoinGlobalCopies = ST.enableMachineScheduler(); 2205 else 2206 JoinGlobalCopies = (EnableGlobalCopies == cl::BOU_TRUE); 2207 2208 // The MachineScheduler does not currently require JoinSplitEdges. This will 2209 // either be enabled unconditionally or replaced by a more general live range 2210 // splitting optimization. 2211 JoinSplitEdges = EnableJoinSplits; 2212 2213 DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n" 2214 << "********** Function: " << MF->getName() << '\n'); 2215 2216 if (VerifyCoalescing) 2217 MF->verify(this, "Before register coalescing"); 2218 2219 RegClassInfo.runOnMachineFunction(fn); 2220 2221 // Join (coalesce) intervals if requested. 2222 if (EnableJoining) 2223 joinAllIntervals(); 2224 2225 // After deleting a lot of copies, register classes may be less constrained. 2226 // Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 -> 2227 // DPR inflation. 2228 array_pod_sort(InflateRegs.begin(), InflateRegs.end()); 2229 InflateRegs.erase(std::unique(InflateRegs.begin(), InflateRegs.end()), 2230 InflateRegs.end()); 2231 DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size() << " regs.\n"); 2232 for (unsigned i = 0, e = InflateRegs.size(); i != e; ++i) { 2233 unsigned Reg = InflateRegs[i]; 2234 if (MRI->reg_nodbg_empty(Reg)) 2235 continue; 2236 if (MRI->recomputeRegClass(Reg, *TM)) { 2237 DEBUG(dbgs() << PrintReg(Reg) << " inflated to " 2238 << MRI->getRegClass(Reg)->getName() << '\n'); 2239 ++NumInflated; 2240 } 2241 } 2242 2243 DEBUG(dump()); 2244 if (VerifyCoalescing) 2245 MF->verify(this, "After register coalescing"); 2246 return true; 2247} 2248 2249/// print - Implement the dump method. 2250void RegisterCoalescer::print(raw_ostream &O, const Module* m) const { 2251 LIS->print(O, m); 2252} 2253