RegisterCoalescer.cpp revision 263508
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. 'B1' in 438 // the example above. 439 LiveInterval::iterator BS = IntB.FindSegmentContaining(CopyIdx); 440 if (BS == IntB.end()) return false; 441 VNInfo *BValNo = BS->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 AS = IntA.FindSegmentContaining(CopyUseIdx); 451 // The live segment might not exist after fun with physreg coalescing. 452 if (AS == IntA.end()) return false; 453 VNInfo *AValNo = AS->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 Segment in IntB that this value number starts with. 463 LiveInterval::iterator ValS = 464 IntB.FindSegmentContaining(AValNo->def.getPrevSlot()); 465 if (ValS == IntB.end()) 466 return false; 467 468 // Make sure that the end of the live segment is inside the same block as 469 // CopyMI. 470 MachineInstr *ValSEndInst = 471 LIS->getInstructionFromIndex(ValS->end.getPrevSlot()); 472 if (!ValSEndInst || ValSEndInst->getParent() != CopyMI->getParent()) 473 return false; 474 475 // Okay, we now know that ValS ends in the same block that the CopyMI 476 // live-range starts. If there are no intervening live segments between them 477 // in IntB, we can merge them. 478 if (ValS+1 != BS) return false; 479 480 DEBUG(dbgs() << "Extending: " << PrintReg(IntB.reg, TRI)); 481 482 SlotIndex FillerStart = ValS->end, FillerEnd = BS->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 // [ValS.end, BS.begin) of either value number, then we merge the 490 // two value numbers. 491 IntB.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, BValNo)); 492 493 // Okay, merge "B1" into the same value number as "B0". 494 if (BValNo != ValS->valno) 495 IntB.MergeValueNumberInto(BValNo, ValS->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 = ValSEndInst->findRegisterUseOperandIdx(IntB.reg, true); 501 if (UIdx != -1) { 502 ValSEndInst->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 (AS->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::iterator BI = 531 std::upper_bound(IntB.begin(), IntB.end(), AI->start); 532 if (BI != IntB.begin()) 533 --BI; 534 for (; BI != IntB.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 || !IntB.Query(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 US = IntA.FindSegmentContaining(UseIdx); 631 if (US == IntA.end() || US->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 US = IntA.FindSegmentContaining(UseIdx); 683 if (US == IntA.end() || US->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 segments 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.addSegment(LiveInterval::Segment(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 = SrcInt.Query(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 (LiveRange *LR = LIS->getCachedRegUnit(*Units)) 878 LR->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 LiveQueryResult LRQ = LI.Query(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()).size() > 1093 LIS->getInterval(CP.getDstReg()).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 segments, do so 1111 // now. 1112 if (!CP.isPartial() && !CP.isPhys()) { 1113 if (adjustCopiesBackFrom(CP, CopyMI) || 1114 removeCopyByCommutingDef(CP, CopyMI)) { 1115 LIS->RemoveMachineInstrFromMaps(CopyMI); 1116 CopyMI->eraseFromParent(); 1117 DEBUG(dbgs() << "\tTrivial!\n"); 1118 return true; 1119 } 1120 } 1121 1122 // Otherwise, we are unable to join the intervals. 1123 DEBUG(dbgs() << "\tInterference!\n"); 1124 Again = true; // May be possible to coalesce later. 1125 return false; 1126 } 1127 1128 // Coalescing to a virtual register that is of a sub-register class of the 1129 // other. Make sure the resulting register is set to the right register class. 1130 if (CP.isCrossClass()) { 1131 ++numCrossRCs; 1132 MRI->setRegClass(CP.getDstReg(), CP.getNewRC()); 1133 } 1134 1135 // Removing sub-register copies can ease the register class constraints. 1136 // Make sure we attempt to inflate the register class of DstReg. 1137 if (!CP.isPhys() && RegClassInfo.isProperSubClass(CP.getNewRC())) 1138 InflateRegs.push_back(CP.getDstReg()); 1139 1140 // CopyMI has been erased by joinIntervals at this point. Remove it from 1141 // ErasedInstrs since copyCoalesceWorkList() won't add a successful join back 1142 // to the work list. This keeps ErasedInstrs from growing needlessly. 1143 ErasedInstrs.erase(CopyMI); 1144 1145 // Rewrite all SrcReg operands to DstReg. 1146 // Also update DstReg operands to include DstIdx if it is set. 1147 if (CP.getDstIdx()) 1148 updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx()); 1149 updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx()); 1150 1151 // SrcReg is guaranteed to be the register whose live interval that is 1152 // being merged. 1153 LIS->removeInterval(CP.getSrcReg()); 1154 1155 // Update regalloc hint. 1156 TRI->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF); 1157 1158 DEBUG({ 1159 dbgs() << "\tJoined. Result = "; 1160 if (CP.isPhys()) 1161 dbgs() << PrintReg(CP.getDstReg(), TRI); 1162 else 1163 dbgs() << LIS->getInterval(CP.getDstReg()); 1164 dbgs() << '\n'; 1165 }); 1166 1167 ++numJoins; 1168 return true; 1169} 1170 1171/// Attempt joining with a reserved physreg. 1172bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) { 1173 assert(CP.isPhys() && "Must be a physreg copy"); 1174 assert(MRI->isReserved(CP.getDstReg()) && "Not a reserved register"); 1175 LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1176 DEBUG(dbgs() << "\t\tRHS = " << RHS << '\n'); 1177 1178 assert(CP.isFlipped() && RHS.containsOneValue() && 1179 "Invalid join with reserved register"); 1180 1181 // Optimization for reserved registers like ESP. We can only merge with a 1182 // reserved physreg if RHS has a single value that is a copy of CP.DstReg(). 1183 // The live range of the reserved register will look like a set of dead defs 1184 // - we don't properly track the live range of reserved registers. 1185 1186 // Deny any overlapping intervals. This depends on all the reserved 1187 // register live ranges to look like dead defs. 1188 for (MCRegUnitIterator UI(CP.getDstReg(), TRI); UI.isValid(); ++UI) 1189 if (RHS.overlaps(LIS->getRegUnit(*UI))) { 1190 DEBUG(dbgs() << "\t\tInterference: " << PrintRegUnit(*UI, TRI) << '\n'); 1191 return false; 1192 } 1193 1194 // Skip any value computations, we are not adding new values to the 1195 // reserved register. Also skip merging the live ranges, the reserved 1196 // register live range doesn't need to be accurate as long as all the 1197 // defs are there. 1198 1199 // Delete the identity copy. 1200 MachineInstr *CopyMI = MRI->getVRegDef(RHS.reg); 1201 LIS->RemoveMachineInstrFromMaps(CopyMI); 1202 CopyMI->eraseFromParent(); 1203 1204 // We don't track kills for reserved registers. 1205 MRI->clearKillFlags(CP.getSrcReg()); 1206 1207 return true; 1208} 1209 1210//===----------------------------------------------------------------------===// 1211// Interference checking and interval joining 1212//===----------------------------------------------------------------------===// 1213// 1214// In the easiest case, the two live ranges being joined are disjoint, and 1215// there is no interference to consider. It is quite common, though, to have 1216// overlapping live ranges, and we need to check if the interference can be 1217// resolved. 1218// 1219// The live range of a single SSA value forms a sub-tree of the dominator tree. 1220// This means that two SSA values overlap if and only if the def of one value 1221// is contained in the live range of the other value. As a special case, the 1222// overlapping values can be defined at the same index. 1223// 1224// The interference from an overlapping def can be resolved in these cases: 1225// 1226// 1. Coalescable copies. The value is defined by a copy that would become an 1227// identity copy after joining SrcReg and DstReg. The copy instruction will 1228// be removed, and the value will be merged with the source value. 1229// 1230// There can be several copies back and forth, causing many values to be 1231// merged into one. We compute a list of ultimate values in the joined live 1232// range as well as a mappings from the old value numbers. 1233// 1234// 2. IMPLICIT_DEF. This instruction is only inserted to ensure all PHI 1235// predecessors have a live out value. It doesn't cause real interference, 1236// and can be merged into the value it overlaps. Like a coalescable copy, it 1237// can be erased after joining. 1238// 1239// 3. Copy of external value. The overlapping def may be a copy of a value that 1240// is already in the other register. This is like a coalescable copy, but 1241// the live range of the source register must be trimmed after erasing the 1242// copy instruction: 1243// 1244// %src = COPY %ext 1245// %dst = COPY %ext <-- Remove this COPY, trim the live range of %ext. 1246// 1247// 4. Clobbering undefined lanes. Vector registers are sometimes built by 1248// defining one lane at a time: 1249// 1250// %dst:ssub0<def,read-undef> = FOO 1251// %src = BAR 1252// %dst:ssub1<def> = COPY %src 1253// 1254// The live range of %src overlaps the %dst value defined by FOO, but 1255// merging %src into %dst:ssub1 is only going to clobber the ssub1 lane 1256// which was undef anyway. 1257// 1258// The value mapping is more complicated in this case. The final live range 1259// will have different value numbers for both FOO and BAR, but there is no 1260// simple mapping from old to new values. It may even be necessary to add 1261// new PHI values. 1262// 1263// 5. Clobbering dead lanes. A def may clobber a lane of a vector register that 1264// is live, but never read. This can happen because we don't compute 1265// individual live ranges per lane. 1266// 1267// %dst<def> = FOO 1268// %src = BAR 1269// %dst:ssub1<def> = COPY %src 1270// 1271// This kind of interference is only resolved locally. If the clobbered 1272// lane value escapes the block, the join is aborted. 1273 1274namespace { 1275/// Track information about values in a single virtual register about to be 1276/// joined. Objects of this class are always created in pairs - one for each 1277/// side of the CoalescerPair. 1278class JoinVals { 1279 LiveInterval &LI; 1280 1281 // Location of this register in the final joined register. 1282 // Either CP.DstIdx or CP.SrcIdx. 1283 unsigned SubIdx; 1284 1285 // Values that will be present in the final live range. 1286 SmallVectorImpl<VNInfo*> &NewVNInfo; 1287 1288 const CoalescerPair &CP; 1289 LiveIntervals *LIS; 1290 SlotIndexes *Indexes; 1291 const TargetRegisterInfo *TRI; 1292 1293 // Value number assignments. Maps value numbers in LI to entries in NewVNInfo. 1294 // This is suitable for passing to LiveInterval::join(). 1295 SmallVector<int, 8> Assignments; 1296 1297 // Conflict resolution for overlapping values. 1298 enum ConflictResolution { 1299 // No overlap, simply keep this value. 1300 CR_Keep, 1301 1302 // Merge this value into OtherVNI and erase the defining instruction. 1303 // Used for IMPLICIT_DEF, coalescable copies, and copies from external 1304 // values. 1305 CR_Erase, 1306 1307 // Merge this value into OtherVNI but keep the defining instruction. 1308 // This is for the special case where OtherVNI is defined by the same 1309 // instruction. 1310 CR_Merge, 1311 1312 // Keep this value, and have it replace OtherVNI where possible. This 1313 // complicates value mapping since OtherVNI maps to two different values 1314 // before and after this def. 1315 // Used when clobbering undefined or dead lanes. 1316 CR_Replace, 1317 1318 // Unresolved conflict. Visit later when all values have been mapped. 1319 CR_Unresolved, 1320 1321 // Unresolvable conflict. Abort the join. 1322 CR_Impossible 1323 }; 1324 1325 // Per-value info for LI. The lane bit masks are all relative to the final 1326 // joined register, so they can be compared directly between SrcReg and 1327 // DstReg. 1328 struct Val { 1329 ConflictResolution Resolution; 1330 1331 // Lanes written by this def, 0 for unanalyzed values. 1332 unsigned WriteLanes; 1333 1334 // Lanes with defined values in this register. Other lanes are undef and 1335 // safe to clobber. 1336 unsigned ValidLanes; 1337 1338 // Value in LI being redefined by this def. 1339 VNInfo *RedefVNI; 1340 1341 // Value in the other live range that overlaps this def, if any. 1342 VNInfo *OtherVNI; 1343 1344 // Is this value an IMPLICIT_DEF that can be erased? 1345 // 1346 // IMPLICIT_DEF values should only exist at the end of a basic block that 1347 // is a predecessor to a phi-value. These IMPLICIT_DEF instructions can be 1348 // safely erased if they are overlapping a live value in the other live 1349 // interval. 1350 // 1351 // Weird control flow graphs and incomplete PHI handling in 1352 // ProcessImplicitDefs can very rarely create IMPLICIT_DEF values with 1353 // longer live ranges. Such IMPLICIT_DEF values should be treated like 1354 // normal values. 1355 bool ErasableImplicitDef; 1356 1357 // True when the live range of this value will be pruned because of an 1358 // overlapping CR_Replace value in the other live range. 1359 bool Pruned; 1360 1361 // True once Pruned above has been computed. 1362 bool PrunedComputed; 1363 1364 Val() : Resolution(CR_Keep), WriteLanes(0), ValidLanes(0), 1365 RedefVNI(0), OtherVNI(0), ErasableImplicitDef(false), 1366 Pruned(false), PrunedComputed(false) {} 1367 1368 bool isAnalyzed() const { return WriteLanes != 0; } 1369 }; 1370 1371 // One entry per value number in LI. 1372 SmallVector<Val, 8> Vals; 1373 1374 unsigned computeWriteLanes(const MachineInstr *DefMI, bool &Redef); 1375 VNInfo *stripCopies(VNInfo *VNI); 1376 ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other); 1377 void computeAssignment(unsigned ValNo, JoinVals &Other); 1378 bool taintExtent(unsigned, unsigned, JoinVals&, 1379 SmallVectorImpl<std::pair<SlotIndex, unsigned> >&); 1380 bool usesLanes(MachineInstr *MI, unsigned, unsigned, unsigned); 1381 bool isPrunedValue(unsigned ValNo, JoinVals &Other); 1382 1383public: 1384 JoinVals(LiveInterval &li, unsigned subIdx, 1385 SmallVectorImpl<VNInfo*> &newVNInfo, 1386 const CoalescerPair &cp, 1387 LiveIntervals *lis, 1388 const TargetRegisterInfo *tri) 1389 : LI(li), SubIdx(subIdx), NewVNInfo(newVNInfo), CP(cp), LIS(lis), 1390 Indexes(LIS->getSlotIndexes()), TRI(tri), 1391 Assignments(LI.getNumValNums(), -1), Vals(LI.getNumValNums()) 1392 {} 1393 1394 /// Analyze defs in LI and compute a value mapping in NewVNInfo. 1395 /// Returns false if any conflicts were impossible to resolve. 1396 bool mapValues(JoinVals &Other); 1397 1398 /// Try to resolve conflicts that require all values to be mapped. 1399 /// Returns false if any conflicts were impossible to resolve. 1400 bool resolveConflicts(JoinVals &Other); 1401 1402 /// Prune the live range of values in Other.LI where they would conflict with 1403 /// CR_Replace values in LI. Collect end points for restoring the live range 1404 /// after joining. 1405 void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints); 1406 1407 /// Erase any machine instructions that have been coalesced away. 1408 /// Add erased instructions to ErasedInstrs. 1409 /// Add foreign virtual registers to ShrinkRegs if their live range ended at 1410 /// the erased instrs. 1411 void eraseInstrs(SmallPtrSet<MachineInstr*, 8> &ErasedInstrs, 1412 SmallVectorImpl<unsigned> &ShrinkRegs); 1413 1414 /// Get the value assignments suitable for passing to LiveInterval::join. 1415 const int *getAssignments() const { return Assignments.data(); } 1416}; 1417} // end anonymous namespace 1418 1419/// Compute the bitmask of lanes actually written by DefMI. 1420/// Set Redef if there are any partial register definitions that depend on the 1421/// previous value of the register. 1422unsigned JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef) { 1423 unsigned L = 0; 1424 for (ConstMIOperands MO(DefMI); MO.isValid(); ++MO) { 1425 if (!MO->isReg() || MO->getReg() != LI.reg || !MO->isDef()) 1426 continue; 1427 L |= TRI->getSubRegIndexLaneMask( 1428 TRI->composeSubRegIndices(SubIdx, MO->getSubReg())); 1429 if (MO->readsReg()) 1430 Redef = true; 1431 } 1432 return L; 1433} 1434 1435/// Find the ultimate value that VNI was copied from. 1436VNInfo *JoinVals::stripCopies(VNInfo *VNI) { 1437 while (!VNI->isPHIDef()) { 1438 MachineInstr *MI = Indexes->getInstructionFromIndex(VNI->def); 1439 assert(MI && "No defining instruction"); 1440 if (!MI->isFullCopy()) 1441 break; 1442 unsigned Reg = MI->getOperand(1).getReg(); 1443 if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1444 break; 1445 LiveQueryResult LRQ = LIS->getInterval(Reg).Query(VNI->def); 1446 if (!LRQ.valueIn()) 1447 break; 1448 VNI = LRQ.valueIn(); 1449 } 1450 return VNI; 1451} 1452 1453/// Analyze ValNo in this live range, and set all fields of Vals[ValNo]. 1454/// Return a conflict resolution when possible, but leave the hard cases as 1455/// CR_Unresolved. 1456/// Recursively calls computeAssignment() on this and Other, guaranteeing that 1457/// both OtherVNI and RedefVNI have been analyzed and mapped before returning. 1458/// The recursion always goes upwards in the dominator tree, making loops 1459/// impossible. 1460JoinVals::ConflictResolution 1461JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) { 1462 Val &V = Vals[ValNo]; 1463 assert(!V.isAnalyzed() && "Value has already been analyzed!"); 1464 VNInfo *VNI = LI.getValNumInfo(ValNo); 1465 if (VNI->isUnused()) { 1466 V.WriteLanes = ~0u; 1467 return CR_Keep; 1468 } 1469 1470 // Get the instruction defining this value, compute the lanes written. 1471 const MachineInstr *DefMI = 0; 1472 if (VNI->isPHIDef()) { 1473 // Conservatively assume that all lanes in a PHI are valid. 1474 V.ValidLanes = V.WriteLanes = TRI->getSubRegIndexLaneMask(SubIdx); 1475 } else { 1476 DefMI = Indexes->getInstructionFromIndex(VNI->def); 1477 bool Redef = false; 1478 V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef); 1479 1480 // If this is a read-modify-write instruction, there may be more valid 1481 // lanes than the ones written by this instruction. 1482 // This only covers partial redef operands. DefMI may have normal use 1483 // operands reading the register. They don't contribute valid lanes. 1484 // 1485 // This adds ssub1 to the set of valid lanes in %src: 1486 // 1487 // %src:ssub1<def> = FOO 1488 // 1489 // This leaves only ssub1 valid, making any other lanes undef: 1490 // 1491 // %src:ssub1<def,read-undef> = FOO %src:ssub2 1492 // 1493 // The <read-undef> flag on the def operand means that old lane values are 1494 // not important. 1495 if (Redef) { 1496 V.RedefVNI = LI.Query(VNI->def).valueIn(); 1497 assert(V.RedefVNI && "Instruction is reading nonexistent value"); 1498 computeAssignment(V.RedefVNI->id, Other); 1499 V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes; 1500 } 1501 1502 // An IMPLICIT_DEF writes undef values. 1503 if (DefMI->isImplicitDef()) { 1504 // We normally expect IMPLICIT_DEF values to be live only until the end 1505 // of their block. If the value is really live longer and gets pruned in 1506 // another block, this flag is cleared again. 1507 V.ErasableImplicitDef = true; 1508 V.ValidLanes &= ~V.WriteLanes; 1509 } 1510 } 1511 1512 // Find the value in Other that overlaps VNI->def, if any. 1513 LiveQueryResult OtherLRQ = Other.LI.Query(VNI->def); 1514 1515 // It is possible that both values are defined by the same instruction, or 1516 // the values are PHIs defined in the same block. When that happens, the two 1517 // values should be merged into one, but not into any preceding value. 1518 // The first value defined or visited gets CR_Keep, the other gets CR_Merge. 1519 if (VNInfo *OtherVNI = OtherLRQ.valueDefined()) { 1520 assert(SlotIndex::isSameInstr(VNI->def, OtherVNI->def) && "Broken LRQ"); 1521 1522 // One value stays, the other is merged. Keep the earlier one, or the first 1523 // one we see. 1524 if (OtherVNI->def < VNI->def) 1525 Other.computeAssignment(OtherVNI->id, *this); 1526 else if (VNI->def < OtherVNI->def && OtherLRQ.valueIn()) { 1527 // This is an early-clobber def overlapping a live-in value in the other 1528 // register. Not mergeable. 1529 V.OtherVNI = OtherLRQ.valueIn(); 1530 return CR_Impossible; 1531 } 1532 V.OtherVNI = OtherVNI; 1533 Val &OtherV = Other.Vals[OtherVNI->id]; 1534 // Keep this value, check for conflicts when analyzing OtherVNI. 1535 if (!OtherV.isAnalyzed()) 1536 return CR_Keep; 1537 // Both sides have been analyzed now. 1538 // Allow overlapping PHI values. Any real interference would show up in a 1539 // predecessor, the PHI itself can't introduce any conflicts. 1540 if (VNI->isPHIDef()) 1541 return CR_Merge; 1542 if (V.ValidLanes & OtherV.ValidLanes) 1543 // Overlapping lanes can't be resolved. 1544 return CR_Impossible; 1545 else 1546 return CR_Merge; 1547 } 1548 1549 // No simultaneous def. Is Other live at the def? 1550 V.OtherVNI = OtherLRQ.valueIn(); 1551 if (!V.OtherVNI) 1552 // No overlap, no conflict. 1553 return CR_Keep; 1554 1555 assert(!SlotIndex::isSameInstr(VNI->def, V.OtherVNI->def) && "Broken LRQ"); 1556 1557 // We have overlapping values, or possibly a kill of Other. 1558 // Recursively compute assignments up the dominator tree. 1559 Other.computeAssignment(V.OtherVNI->id, *this); 1560 Val &OtherV = Other.Vals[V.OtherVNI->id]; 1561 1562 // Check if OtherV is an IMPLICIT_DEF that extends beyond its basic block. 1563 // This shouldn't normally happen, but ProcessImplicitDefs can leave such 1564 // IMPLICIT_DEF instructions behind, and there is nothing wrong with it 1565 // technically. 1566 // 1567 // WHen it happens, treat that IMPLICIT_DEF as a normal value, and don't try 1568 // to erase the IMPLICIT_DEF instruction. 1569 if (OtherV.ErasableImplicitDef && DefMI && 1570 DefMI->getParent() != Indexes->getMBBFromIndex(V.OtherVNI->def)) { 1571 DEBUG(dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->def 1572 << " extends into BB#" << DefMI->getParent()->getNumber() 1573 << ", keeping it.\n"); 1574 OtherV.ErasableImplicitDef = false; 1575 } 1576 1577 // Allow overlapping PHI values. Any real interference would show up in a 1578 // predecessor, the PHI itself can't introduce any conflicts. 1579 if (VNI->isPHIDef()) 1580 return CR_Replace; 1581 1582 // Check for simple erasable conflicts. 1583 if (DefMI->isImplicitDef()) 1584 return CR_Erase; 1585 1586 // Include the non-conflict where DefMI is a coalescable copy that kills 1587 // OtherVNI. We still want the copy erased and value numbers merged. 1588 if (CP.isCoalescable(DefMI)) { 1589 // Some of the lanes copied from OtherVNI may be undef, making them undef 1590 // here too. 1591 V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes; 1592 return CR_Erase; 1593 } 1594 1595 // This may not be a real conflict if DefMI simply kills Other and defines 1596 // VNI. 1597 if (OtherLRQ.isKill() && OtherLRQ.endPoint() <= VNI->def) 1598 return CR_Keep; 1599 1600 // Handle the case where VNI and OtherVNI can be proven to be identical: 1601 // 1602 // %other = COPY %ext 1603 // %this = COPY %ext <-- Erase this copy 1604 // 1605 if (DefMI->isFullCopy() && !CP.isPartial() && 1606 stripCopies(VNI) == stripCopies(V.OtherVNI)) 1607 return CR_Erase; 1608 1609 // If the lanes written by this instruction were all undef in OtherVNI, it is 1610 // still safe to join the live ranges. This can't be done with a simple value 1611 // mapping, though - OtherVNI will map to multiple values: 1612 // 1613 // 1 %dst:ssub0 = FOO <-- OtherVNI 1614 // 2 %src = BAR <-- VNI 1615 // 3 %dst:ssub1 = COPY %src<kill> <-- Eliminate this copy. 1616 // 4 BAZ %dst<kill> 1617 // 5 QUUX %src<kill> 1618 // 1619 // Here OtherVNI will map to itself in [1;2), but to VNI in [2;5). CR_Replace 1620 // handles this complex value mapping. 1621 if ((V.WriteLanes & OtherV.ValidLanes) == 0) 1622 return CR_Replace; 1623 1624 // If the other live range is killed by DefMI and the live ranges are still 1625 // overlapping, it must be because we're looking at an early clobber def: 1626 // 1627 // %dst<def,early-clobber> = ASM %src<kill> 1628 // 1629 // In this case, it is illegal to merge the two live ranges since the early 1630 // clobber def would clobber %src before it was read. 1631 if (OtherLRQ.isKill()) { 1632 // This case where the def doesn't overlap the kill is handled above. 1633 assert(VNI->def.isEarlyClobber() && 1634 "Only early clobber defs can overlap a kill"); 1635 return CR_Impossible; 1636 } 1637 1638 // VNI is clobbering live lanes in OtherVNI, but there is still the 1639 // possibility that no instructions actually read the clobbered lanes. 1640 // If we're clobbering all the lanes in OtherVNI, at least one must be read. 1641 // Otherwise Other.LI wouldn't be live here. 1642 if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes) == 0) 1643 return CR_Impossible; 1644 1645 // We need to verify that no instructions are reading the clobbered lanes. To 1646 // save compile time, we'll only check that locally. Don't allow the tainted 1647 // value to escape the basic block. 1648 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1649 if (OtherLRQ.endPoint() >= Indexes->getMBBEndIdx(MBB)) 1650 return CR_Impossible; 1651 1652 // There are still some things that could go wrong besides clobbered lanes 1653 // being read, for example OtherVNI may be only partially redefined in MBB, 1654 // and some clobbered lanes could escape the block. Save this analysis for 1655 // resolveConflicts() when all values have been mapped. We need to know 1656 // RedefVNI and WriteLanes for any later defs in MBB, and we can't compute 1657 // that now - the recursive analyzeValue() calls must go upwards in the 1658 // dominator tree. 1659 return CR_Unresolved; 1660} 1661 1662/// Compute the value assignment for ValNo in LI. 1663/// This may be called recursively by analyzeValue(), but never for a ValNo on 1664/// the stack. 1665void JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) { 1666 Val &V = Vals[ValNo]; 1667 if (V.isAnalyzed()) { 1668 // Recursion should always move up the dominator tree, so ValNo is not 1669 // supposed to reappear before it has been assigned. 1670 assert(Assignments[ValNo] != -1 && "Bad recursion?"); 1671 return; 1672 } 1673 switch ((V.Resolution = analyzeValue(ValNo, Other))) { 1674 case CR_Erase: 1675 case CR_Merge: 1676 // Merge this ValNo into OtherVNI. 1677 assert(V.OtherVNI && "OtherVNI not assigned, can't merge."); 1678 assert(Other.Vals[V.OtherVNI->id].isAnalyzed() && "Missing recursion"); 1679 Assignments[ValNo] = Other.Assignments[V.OtherVNI->id]; 1680 DEBUG(dbgs() << "\t\tmerge " << PrintReg(LI.reg) << ':' << ValNo << '@' 1681 << LI.getValNumInfo(ValNo)->def << " into " 1682 << PrintReg(Other.LI.reg) << ':' << V.OtherVNI->id << '@' 1683 << V.OtherVNI->def << " --> @" 1684 << NewVNInfo[Assignments[ValNo]]->def << '\n'); 1685 break; 1686 case CR_Replace: 1687 case CR_Unresolved: 1688 // The other value is going to be pruned if this join is successful. 1689 assert(V.OtherVNI && "OtherVNI not assigned, can't prune"); 1690 Other.Vals[V.OtherVNI->id].Pruned = true; 1691 // Fall through. 1692 default: 1693 // This value number needs to go in the final joined live range. 1694 Assignments[ValNo] = NewVNInfo.size(); 1695 NewVNInfo.push_back(LI.getValNumInfo(ValNo)); 1696 break; 1697 } 1698} 1699 1700bool JoinVals::mapValues(JoinVals &Other) { 1701 for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1702 computeAssignment(i, Other); 1703 if (Vals[i].Resolution == CR_Impossible) { 1704 DEBUG(dbgs() << "\t\tinterference at " << PrintReg(LI.reg) << ':' << i 1705 << '@' << LI.getValNumInfo(i)->def << '\n'); 1706 return false; 1707 } 1708 } 1709 return true; 1710} 1711 1712/// Assuming ValNo is going to clobber some valid lanes in Other.LI, compute 1713/// the extent of the tainted lanes in the block. 1714/// 1715/// Multiple values in Other.LI can be affected since partial redefinitions can 1716/// preserve previously tainted lanes. 1717/// 1718/// 1 %dst = VLOAD <-- Define all lanes in %dst 1719/// 2 %src = FOO <-- ValNo to be joined with %dst:ssub0 1720/// 3 %dst:ssub1 = BAR <-- Partial redef doesn't clear taint in ssub0 1721/// 4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read 1722/// 1723/// For each ValNo in Other that is affected, add an (EndIndex, TaintedLanes) 1724/// entry to TaintedVals. 1725/// 1726/// Returns false if the tainted lanes extend beyond the basic block. 1727bool JoinVals:: 1728taintExtent(unsigned ValNo, unsigned TaintedLanes, JoinVals &Other, 1729 SmallVectorImpl<std::pair<SlotIndex, unsigned> > &TaintExtent) { 1730 VNInfo *VNI = LI.getValNumInfo(ValNo); 1731 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1732 SlotIndex MBBEnd = Indexes->getMBBEndIdx(MBB); 1733 1734 // Scan Other.LI from VNI.def to MBBEnd. 1735 LiveInterval::iterator OtherI = Other.LI.find(VNI->def); 1736 assert(OtherI != Other.LI.end() && "No conflict?"); 1737 do { 1738 // OtherI is pointing to a tainted value. Abort the join if the tainted 1739 // lanes escape the block. 1740 SlotIndex End = OtherI->end; 1741 if (End >= MBBEnd) { 1742 DEBUG(dbgs() << "\t\ttaints global " << PrintReg(Other.LI.reg) << ':' 1743 << OtherI->valno->id << '@' << OtherI->start << '\n'); 1744 return false; 1745 } 1746 DEBUG(dbgs() << "\t\ttaints local " << PrintReg(Other.LI.reg) << ':' 1747 << OtherI->valno->id << '@' << OtherI->start 1748 << " to " << End << '\n'); 1749 // A dead def is not a problem. 1750 if (End.isDead()) 1751 break; 1752 TaintExtent.push_back(std::make_pair(End, TaintedLanes)); 1753 1754 // Check for another def in the MBB. 1755 if (++OtherI == Other.LI.end() || OtherI->start >= MBBEnd) 1756 break; 1757 1758 // Lanes written by the new def are no longer tainted. 1759 const Val &OV = Other.Vals[OtherI->valno->id]; 1760 TaintedLanes &= ~OV.WriteLanes; 1761 if (!OV.RedefVNI) 1762 break; 1763 } while (TaintedLanes); 1764 return true; 1765} 1766 1767/// Return true if MI uses any of the given Lanes from Reg. 1768/// This does not include partial redefinitions of Reg. 1769bool JoinVals::usesLanes(MachineInstr *MI, unsigned Reg, unsigned SubIdx, 1770 unsigned Lanes) { 1771 if (MI->isDebugValue()) 1772 return false; 1773 for (ConstMIOperands MO(MI); MO.isValid(); ++MO) { 1774 if (!MO->isReg() || MO->isDef() || MO->getReg() != Reg) 1775 continue; 1776 if (!MO->readsReg()) 1777 continue; 1778 if (Lanes & TRI->getSubRegIndexLaneMask( 1779 TRI->composeSubRegIndices(SubIdx, MO->getSubReg()))) 1780 return true; 1781 } 1782 return false; 1783} 1784 1785bool JoinVals::resolveConflicts(JoinVals &Other) { 1786 for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1787 Val &V = Vals[i]; 1788 assert (V.Resolution != CR_Impossible && "Unresolvable conflict"); 1789 if (V.Resolution != CR_Unresolved) 1790 continue; 1791 DEBUG(dbgs() << "\t\tconflict at " << PrintReg(LI.reg) << ':' << i 1792 << '@' << LI.getValNumInfo(i)->def << '\n'); 1793 ++NumLaneConflicts; 1794 assert(V.OtherVNI && "Inconsistent conflict resolution."); 1795 VNInfo *VNI = LI.getValNumInfo(i); 1796 const Val &OtherV = Other.Vals[V.OtherVNI->id]; 1797 1798 // VNI is known to clobber some lanes in OtherVNI. If we go ahead with the 1799 // join, those lanes will be tainted with a wrong value. Get the extent of 1800 // the tainted lanes. 1801 unsigned TaintedLanes = V.WriteLanes & OtherV.ValidLanes; 1802 SmallVector<std::pair<SlotIndex, unsigned>, 8> TaintExtent; 1803 if (!taintExtent(i, TaintedLanes, Other, TaintExtent)) 1804 // Tainted lanes would extend beyond the basic block. 1805 return false; 1806 1807 assert(!TaintExtent.empty() && "There should be at least one conflict."); 1808 1809 // Now look at the instructions from VNI->def to TaintExtent (inclusive). 1810 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1811 MachineBasicBlock::iterator MI = MBB->begin(); 1812 if (!VNI->isPHIDef()) { 1813 MI = Indexes->getInstructionFromIndex(VNI->def); 1814 // No need to check the instruction defining VNI for reads. 1815 ++MI; 1816 } 1817 assert(!SlotIndex::isSameInstr(VNI->def, TaintExtent.front().first) && 1818 "Interference ends on VNI->def. Should have been handled earlier"); 1819 MachineInstr *LastMI = 1820 Indexes->getInstructionFromIndex(TaintExtent.front().first); 1821 assert(LastMI && "Range must end at a proper instruction"); 1822 unsigned TaintNum = 0; 1823 for(;;) { 1824 assert(MI != MBB->end() && "Bad LastMI"); 1825 if (usesLanes(MI, Other.LI.reg, Other.SubIdx, TaintedLanes)) { 1826 DEBUG(dbgs() << "\t\ttainted lanes used by: " << *MI); 1827 return false; 1828 } 1829 // LastMI is the last instruction to use the current value. 1830 if (&*MI == LastMI) { 1831 if (++TaintNum == TaintExtent.size()) 1832 break; 1833 LastMI = Indexes->getInstructionFromIndex(TaintExtent[TaintNum].first); 1834 assert(LastMI && "Range must end at a proper instruction"); 1835 TaintedLanes = TaintExtent[TaintNum].second; 1836 } 1837 ++MI; 1838 } 1839 1840 // The tainted lanes are unused. 1841 V.Resolution = CR_Replace; 1842 ++NumLaneResolves; 1843 } 1844 return true; 1845} 1846 1847// Determine if ValNo is a copy of a value number in LI or Other.LI that will 1848// be pruned: 1849// 1850// %dst = COPY %src 1851// %src = COPY %dst <-- This value to be pruned. 1852// %dst = COPY %src <-- This value is a copy of a pruned value. 1853// 1854bool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) { 1855 Val &V = Vals[ValNo]; 1856 if (V.Pruned || V.PrunedComputed) 1857 return V.Pruned; 1858 1859 if (V.Resolution != CR_Erase && V.Resolution != CR_Merge) 1860 return V.Pruned; 1861 1862 // Follow copies up the dominator tree and check if any intermediate value 1863 // has been pruned. 1864 V.PrunedComputed = true; 1865 V.Pruned = Other.isPrunedValue(V.OtherVNI->id, *this); 1866 return V.Pruned; 1867} 1868 1869void JoinVals::pruneValues(JoinVals &Other, 1870 SmallVectorImpl<SlotIndex> &EndPoints) { 1871 for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1872 SlotIndex Def = LI.getValNumInfo(i)->def; 1873 switch (Vals[i].Resolution) { 1874 case CR_Keep: 1875 break; 1876 case CR_Replace: { 1877 // This value takes precedence over the value in Other.LI. 1878 LIS->pruneValue(&Other.LI, Def, &EndPoints); 1879 // Check if we're replacing an IMPLICIT_DEF value. The IMPLICIT_DEF 1880 // instructions are only inserted to provide a live-out value for PHI 1881 // predecessors, so the instruction should simply go away once its value 1882 // has been replaced. 1883 Val &OtherV = Other.Vals[Vals[i].OtherVNI->id]; 1884 bool EraseImpDef = OtherV.ErasableImplicitDef && 1885 OtherV.Resolution == CR_Keep; 1886 if (!Def.isBlock()) { 1887 // Remove <def,read-undef> flags. This def is now a partial redef. 1888 // Also remove <def,dead> flags since the joined live range will 1889 // continue past this instruction. 1890 for (MIOperands MO(Indexes->getInstructionFromIndex(Def)); 1891 MO.isValid(); ++MO) 1892 if (MO->isReg() && MO->isDef() && MO->getReg() == LI.reg) { 1893 MO->setIsUndef(EraseImpDef); 1894 MO->setIsDead(false); 1895 } 1896 // This value will reach instructions below, but we need to make sure 1897 // the live range also reaches the instruction at Def. 1898 if (!EraseImpDef) 1899 EndPoints.push_back(Def); 1900 } 1901 DEBUG(dbgs() << "\t\tpruned " << PrintReg(Other.LI.reg) << " at " << Def 1902 << ": " << Other.LI << '\n'); 1903 break; 1904 } 1905 case CR_Erase: 1906 case CR_Merge: 1907 if (isPrunedValue(i, Other)) { 1908 // This value is ultimately a copy of a pruned value in LI or Other.LI. 1909 // We can no longer trust the value mapping computed by 1910 // computeAssignment(), the value that was originally copied could have 1911 // been replaced. 1912 LIS->pruneValue(&LI, Def, &EndPoints); 1913 DEBUG(dbgs() << "\t\tpruned all of " << PrintReg(LI.reg) << " at " 1914 << Def << ": " << LI << '\n'); 1915 } 1916 break; 1917 case CR_Unresolved: 1918 case CR_Impossible: 1919 llvm_unreachable("Unresolved conflicts"); 1920 } 1921 } 1922} 1923 1924void JoinVals::eraseInstrs(SmallPtrSet<MachineInstr*, 8> &ErasedInstrs, 1925 SmallVectorImpl<unsigned> &ShrinkRegs) { 1926 for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1927 // Get the def location before markUnused() below invalidates it. 1928 SlotIndex Def = LI.getValNumInfo(i)->def; 1929 switch (Vals[i].Resolution) { 1930 case CR_Keep: 1931 // If an IMPLICIT_DEF value is pruned, it doesn't serve a purpose any 1932 // longer. The IMPLICIT_DEF instructions are only inserted by 1933 // PHIElimination to guarantee that all PHI predecessors have a value. 1934 if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned) 1935 break; 1936 // Remove value number i from LI. Note that this VNInfo is still present 1937 // in NewVNInfo, so it will appear as an unused value number in the final 1938 // joined interval. 1939 LI.getValNumInfo(i)->markUnused(); 1940 LI.removeValNo(LI.getValNumInfo(i)); 1941 DEBUG(dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LI << '\n'); 1942 // FALL THROUGH. 1943 1944 case CR_Erase: { 1945 MachineInstr *MI = Indexes->getInstructionFromIndex(Def); 1946 assert(MI && "No instruction to erase"); 1947 if (MI->isCopy()) { 1948 unsigned Reg = MI->getOperand(1).getReg(); 1949 if (TargetRegisterInfo::isVirtualRegister(Reg) && 1950 Reg != CP.getSrcReg() && Reg != CP.getDstReg()) 1951 ShrinkRegs.push_back(Reg); 1952 } 1953 ErasedInstrs.insert(MI); 1954 DEBUG(dbgs() << "\t\terased:\t" << Def << '\t' << *MI); 1955 LIS->RemoveMachineInstrFromMaps(MI); 1956 MI->eraseFromParent(); 1957 break; 1958 } 1959 default: 1960 break; 1961 } 1962 } 1963} 1964 1965bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) { 1966 SmallVector<VNInfo*, 16> NewVNInfo; 1967 LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1968 LiveInterval &LHS = LIS->getInterval(CP.getDstReg()); 1969 JoinVals RHSVals(RHS, CP.getSrcIdx(), NewVNInfo, CP, LIS, TRI); 1970 JoinVals LHSVals(LHS, CP.getDstIdx(), NewVNInfo, CP, LIS, TRI); 1971 1972 DEBUG(dbgs() << "\t\tRHS = " << RHS 1973 << "\n\t\tLHS = " << LHS 1974 << '\n'); 1975 1976 // First compute NewVNInfo and the simple value mappings. 1977 // Detect impossible conflicts early. 1978 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) 1979 return false; 1980 1981 // Some conflicts can only be resolved after all values have been mapped. 1982 if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals)) 1983 return false; 1984 1985 // All clear, the live ranges can be merged. 1986 1987 // The merging algorithm in LiveInterval::join() can't handle conflicting 1988 // value mappings, so we need to remove any live ranges that overlap a 1989 // CR_Replace resolution. Collect a set of end points that can be used to 1990 // restore the live range after joining. 1991 SmallVector<SlotIndex, 8> EndPoints; 1992 LHSVals.pruneValues(RHSVals, EndPoints); 1993 RHSVals.pruneValues(LHSVals, EndPoints); 1994 1995 // Erase COPY and IMPLICIT_DEF instructions. This may cause some external 1996 // registers to require trimming. 1997 SmallVector<unsigned, 8> ShrinkRegs; 1998 LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs); 1999 RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs); 2000 while (!ShrinkRegs.empty()) 2001 LIS->shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val())); 2002 2003 // Join RHS into LHS. 2004 LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo); 2005 2006 // Kill flags are going to be wrong if the live ranges were overlapping. 2007 // Eventually, we should simply clear all kill flags when computing live 2008 // ranges. They are reinserted after register allocation. 2009 MRI->clearKillFlags(LHS.reg); 2010 MRI->clearKillFlags(RHS.reg); 2011 2012 if (EndPoints.empty()) 2013 return true; 2014 2015 // Recompute the parts of the live range we had to remove because of 2016 // CR_Replace conflicts. 2017 DEBUG(dbgs() << "\t\trestoring liveness to " << EndPoints.size() 2018 << " points: " << LHS << '\n'); 2019 LIS->extendToIndices(LHS, EndPoints); 2020 return true; 2021} 2022 2023/// joinIntervals - Attempt to join these two intervals. On failure, this 2024/// returns false. 2025bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) { 2026 return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP); 2027} 2028 2029namespace { 2030// Information concerning MBB coalescing priority. 2031struct MBBPriorityInfo { 2032 MachineBasicBlock *MBB; 2033 unsigned Depth; 2034 bool IsSplit; 2035 2036 MBBPriorityInfo(MachineBasicBlock *mbb, unsigned depth, bool issplit) 2037 : MBB(mbb), Depth(depth), IsSplit(issplit) {} 2038}; 2039} 2040 2041// C-style comparator that sorts first based on the loop depth of the basic 2042// block (the unsigned), and then on the MBB number. 2043// 2044// EnableGlobalCopies assumes that the primary sort key is loop depth. 2045static int compareMBBPriority(const MBBPriorityInfo *LHS, 2046 const MBBPriorityInfo *RHS) { 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.useMachineScheduler(); 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