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